گراف (Graph) یکی از پر کاربردترین علوم حال حاضر است که در حوزه‌های مختلفی از شبکه‌های کامپیوتری گرفته تا هوش مصنوعی مورد استفاده قرار می‌گیرد. در ساده‌ترین تعریف، گراف‌ها به مجموعه رئوس (گره‌ها) و یال‌هایی (یا لبه‌ها) که بین رئوس قرار می‌گیرند، اشاره دارند. به طور معمول، رئوس نشان دهنده موجودیت‌ها در یک ساختار یا سامانه هستند، در حالی که یال‌ها توصیف کننده ارتباط میان اشیا یا موجودیت‌ها هستند. با این توصیف باید بگوییم که گراف، یک ساختار شماتیک است که باهدف نمایش و بصریسازی ارتباط بین مولفه‌های یک سیستم مورد استفاده قرار می‌گیرد.

گراف چیست؟

گراف در ریاضیات و علوم کامپیوتر، مفهومی است که برای نمایش و توصیف ارتباطات و روابط بین مجموعه‌ای از عناصر استفاده می‌شود. یک گراف می‌تواند شامل یک مجموعه از رئوس یا گره‌ها و یک مجموعه از یال‌ها یا لبه‌ها باشد که ارتباطات بین این رئوس را نشان می‌دهند. در یک گراف، رئوس معمولا موجودیت‌ها یا عناصر مختلف را نمایش می‌دهند و یال‌ها نشان دهنده روابط بین این موجودیت‌ها هستند. به طور مثال، در یک گراف شبکه اجتماعی، هر راس ممکن است یک فرد را نمایش دهد و یال‌ها نشان دهنده دوستی یا روابط دیگر بین افراد باشند. گراف‌ها می‌توانند به صورت ساده یا پیچیده باشند و در انواع مختلفی از مسائل و برنامه‌ها مورد استفاده قرار می‌گیرند. برخی از مفاهیم و ویژگی‌های مهم گراف‌ها عبارتند از.

1. رئوس (گره‌ها): نقاط یا موجودیت‌هایی که در گراف حضور دارند.
2. یال‌ها (لبه‌ها): ارتباطات بین رئوس را نشان می‌دهند. یال‌ها می‌توانند جهت‌دار یا بی‌جهت باشند.
3. درجه راس: تعداد یال‌های متصل به یک رأس را نشان می‌دهد.
4. مسیر: یک دنباله از رئوس و یال‌ها که از یک راس به راس دیگر می‌رود.
5. گراف جهت‌دار: گرافی که یال‌ها جهت دارند و در آن رئوس به صورت مرتب شده هستند.
6. گراف بدون جهت: گرافی که یال‌ها بی‌جهت هستند و رئوس به صورت غیرمرتب قرار دارند.

همچنین، گراف‌ها در برنامه‌نویسی و علوم کامپیوتر برای مدل‌سازی و حل مسائل مختلف مانند شبکه‌ها، الگوریتم‌ها، مسیریابی، تحلیل شبکه‌های اجتماعی و بسیاری دیگر استفاده می‌شوند. گراف‌ها از نظر ساختاری می‌توانند ساده و بدون جهت (به عنوان گراف بی‌جهت) یا جهت‌دار (به عنوان گراف جهت‌دار) باشند. در گراف بی‌جهت، یال‌ها بین رئوس بدون جهت خاصی قرار می‌گیرند، در حالی که در گراف جهت‌دار، یال‌ها دارای جهت خاصی هستند که نشان می‌دهد کدام راس به کدام راس متصل است.

گراف در چه حوزه هایی از علوم استفاده می شود؟

گراف در بسیاری از حوزه‌های علمی و فنی استفاده می‌شود. اولین مورد علوم کامپیوتر است. گراف‌ها در علوم کامپیوتر و به ویژه در الگوریتم و ساختار داده ها استفاده می‌شوند. الگوریتم های گرافی مانند جست‌وجو در عمق (DFS)، جست‌وجوی سطح اولویت (BFS)، الگوریتم دیجکسترا (Dijkstra) و الگوریتم کراسکال (Kruskal) برای حل مسایلی مانند جست‌وجوی کوتاه‌ترین مسیر، پیدا کردن درخت پوشای کمینه و غیره استفاده می‌شوند. همچنین، گراف‌ها به عنوان مدلی برای نمایش و تحلیل شبکه‌ها استفاده می‌شوند. بد نیست بدانید که تئوری گراف به عنوان یک حوزه ریاضی بررسی و ویژگی‌های مختلف گراف‌ها را مورد بررسی قرار می‌دهد. این حوزه شامل مفاهیمی مانند درجه راس، اتصالات، مسیرها، چرخه‌ها، مولفه‌های متصل، گراف‌های اقلیدسی و بسیاری مفاهیم دیگر است. گراف‌ها در ریاضیات برای بررسی و حل مسائل مانند رنگ‌آمیزی گراف، تئوری درخت، گراف‌های همبند و غیره مورد استفاده قرار می‌گیرند. در برنامه‌ریزی ریاضی، گراف‌ها برای مدل‌سازی و حل مسایلی مانند مسایل جریان، مسایل تخصیص منابع، مساله مسیریابی و برنامه‌ریزی زمان‌بندی استفاده می‌شوند. در زمینه روانشناسی و علوم اجتماعی، گراف‌ها مانند شبکه‌های اجتماعی و مدل‌سازی روابط اجتماعی استفاده می‌شوند. گراف‌ها در حوزه‌های دیگری مانند حمل و نقل، شبکه‌های ارتباطی، جغرافیا، خوشه‌بندی داده‌ها، شبکه‌های عصبی، شبکه‌های توزیع برق، مهندسی سیستم‌ها و بسیاری حوزه‌های دیگر نیز استفاده می‌شوند. به طور کلی، گراف‌ها به عنوان یک ابزار قدرتمند در مدل‌سازی، تحلیل و حل مسایل پیچیده در بسیاری از حوزه‌های علمی و فنی استفاده می‌شوند. همچنین، لازم به توضیح است که گراف‌ها در الگوریتم‌های جست‌وجو و مسیریابی بسیار مورد استفاده قرار می‌گیرند. به عنوان مثال، الگوریتم جستجوی عمق اول و جست‌وجوی سطح اول، که در مسایلی مانند جستجوی مسیر کوتاه در یک شبکه، پیدا کردن کلمات کلیدی در یک متن و غیره استفاده می‌شوند، بر روی گراف‌ها عمل می‌کنند.

اصطلاحات مهم مرتبط با گراف‌ها

در زمینه گراف‌ها، تعدادی تعریف و اصطلاح مرتبط با این مفهوم وجود دارد. برخی اصطلاحات مهم در حوزه گراف‌ها به شرح زیر هستند:

رأس (گره): راس یا گره، نقطه‌ای است که در یک گراف وجود دارد و می‌تواند موجودیتی مانند شخص، مکان یا هر مورد دیگر را نمایش دهد.

یال (لبه): یال یا لبه، ارتباط بین دو راس در یک گراف را نشان می‌دهد. یال‌ها می‌توانند جهت دار یا بی‌جهت باشند. در یک گراف جهت‌دار، یال‌ها دارای جهتی مشخص می‌باشند و در گراف بی‌جهت، یال‌ها بدون جهت هستند.

درجه راس: درجه راس، تعداد یال‌هایی است که به یک راس متصل هستند. برای یک گراف جهت‌دار، درجه راس به دو شکل متمایز است: درجه ورودی (تعداد یال‌هایی که به راس وارد می‌شوند) و درجه خروجی (تعداد یال‌هایی که از راس خارج می‌شوند).

مسیر: مسیر، دنباله‌ای است از رأس‌ها و یال‌ها که از یک راس به راس دیگر می‌رود. مسیر می‌تواند جهت‌دار یا بی‌جهت باشد و می‌تواند تکراری رئوس داشته باشد یا نداشته باشد.

چرخه: چرخه، مسیری است که از یک راس شروع شده و به همان راس بازمی‌گردد. چرخه می‌تواند شامل چندین یال و راس باشد و در گراف بی‌جهت، هر چرخه باید حداقل سه راس داشته باشد.

گراف جهت‌دار: گرافی است که یال‌ها جهت دارند و راس‌ها به صورت مرتب شده هستند. این گونه گراف‌ها معمولا در مسایلی که جهت و روابط یک‌طرفه مهم هستند (مانند شبکه‌های ترتیبی) استفاده می‌شوند.

گراف بدون جهت: گرافی است که یال‌ها بی‌جهت هستند و راس‌ها به صورت غیرمرتب قرار دارند. در این نوع گراف‌ها، روابط میان رئوس به صورت دوطرفه و بدون جهت است.

گراف همبند: گراف همبند، گرافی است که بین هر دو رأس در آن یک مسیر وجود داشته باشد. به عبارت دیگر، هر زوج راس در گراف همبند به وسیله یک مسیر قابل دسترسی است.

زیرگراف: زیرگراف، گراف کوچک‌تری است که به‌طور کامل درون گراف بزرگ‌تر قرار دارد. به عبارت دیگر، زیرگراف، زیرمجموعه‌ای از رئوس و یال‌های گراف اصلی است.

گراف جهت‌دار بدون دور: گراف جهت‌دار بدون دور، گرافی است که هیچ چرخه‌ای در آن وجود نداشته باشد. به عبارت دیگر، نمی‌توان از یک راس به خودش با استفاده از یال‌ها پیمود.

گراف‌ها چه ویژگی‌های شاخصی دارند؟

گراف‌ها ساختارهای ریاضی هستند که توصیفی از ارتباطات و ارتباطات بین اجزای مختلف را ارائه می‌دهند. ویژگی‌های اساسی گراف‌ها عبارتند از: رئوس (گره‌ها) که نقاط یا موجودیت‌ها را نمایش می‌دهند، یال‌ها (لبه‌ها) که ارتباطات بین رئوس را نشان می‌دهند و مجموعه‌ای از رئوس و یال‌ها که ساختار اصلی گراف را تشکیل می‌دهند. گراف‌ها می‌توانند جهت‌دار یا بی‌جهت باشند؛ در گراف جهت‌دار، یال‌ها دارای جهت مشخصی هستند و در گراف بی‌جهت، یال‌ها بدون جهت هستند. همچنین، گراف‌ها می‌توانند متصل و همبند باشند؛ گراف متصل، این ویژگی را دارد که بین هر دو راس در آن یک مسیر وجود داشته باشد، در حالی که گراف همبند، همبندی بین تمام رئوس را نشان می‌دهد. این ویژگی‌ها مبنای تحلیل و کاربرد گراف‌ها در مسایل مختلف از جمله شبکه‌ها، الگوریتم‌ها، بهینه‌سازی و مدل‌سازی را فراهم می‌کنند. همچنین، در برخی از گراف‌ها، یال‌ها می‌توانند دارای وزن یا برچسب باشند، که ویژگی‌هایی مانند فاصله، هزینه یا ظرفیت را نشان می‌دهند. علاوه بر این، در گراف‌ها ممکن است مسیرها و دورها وجود داشته باشند، که به ترتیب از یک راس به راس دیگر می‌روند و یا به همان راس برمی‌گردند. همچنین، گراف‌ها ممکن است شامل جزیره‌ها باشند، که مجموعه‌ای از رئوس است که بین هر دو راس در آن مسیری وجود دارد. این ویژگی‌ها می‌توانند در تحلیل و استفاده از گراف‌ها بسیار مفید باشند.

قضیه مجموع مرتبه‌های رئوس

قضیه مجموع مرتبه‌های رئوس، یکی از قضیه‌های مهم در نظریه گراف است که رابطه‌ای بین تعداد رئوس و تعداد یال‌ها در یک گراف بیان می‌کند. برای یک گراف بدون جهت، قضیه مجموع مرتبه‌های رئوس به این صورت بیان می‌شود: در یک گراف بدون جهت با n راس و m یال، مجموع مرتبه‌های رئوس برابر است با 2m. به عبارت دیگر، اگر تعداد رئوس گراف را با n و تعداد یال‌ها را با m نمایش دهیم، آن‌گاه مجموع درجه رئوس گراف بدون جهت برابر است با ضرب تعداد یال‌ها در 2.

این قضیه نشان می‌دهد که در یک گراف بدون جهت، مجموع درجه تمام رئوس برابر است با ضرب دو تعداد یال‌ها. این معادله به این معنی است که هر بار که یک یال از یک راس به راس دیگر اضافه می‌شود، مجموع درجه رئوس به مقدار 2 افزایش پیدا می‌کند. قضیه مجموع مرتبه‌های رئوس در بسیاری از تحلیل‌ها و محاسبات مرتبط با گراف‌ها اهمیت دارد. به عنوان مثال، این قضیه در تحلیل پایداری شبکه‌ها، بهینه‌سازی مسایل و تحلیل الگوریتم‌ها مورد استفاده قرار می‌گیرد. در یک گراف، هر یال به دو راس متصل است و هر راس به یال‌های متصل به خود راس می‌دهد. بنابراین، مجموع درجه رئوس برابر با دو برابر تعداد یال‌ها خواهد بود. قضیه مجموع مرتبه‌های رئوس در تحلیل و استنباط‌های گوناگون استفاده می‌شود. به عنوان مثال، با استفاده از این قضیه، می‌توان تعداد یال‌ها را بر حسب تعداد رئوس و مجموع درجه‌های رئوس محاسبه کرد یا در مسایل مربوط به جست‌وجو در گراف‌ها و تحلیل شبکه‌ها به کار گرفته شود.

گراف‌ها به چه مدل‌هایی تقسیم می‌شوند؟

گراف‌ها به چند گروه طبقه‌بندی می‌شوند. اولین مورد گراف بدون ‌جهت (Undirected Graph) است. در این نوع گراف، یال‌ها بدون جهت هستند، به این معنی که ارتباط بین دو راس قابل توجه است، اما جهت خاصی در این ارتباط تعیین نمی‌شود. مورد بعد گراف جهت‌دار (Directed Graph) است. در این نوع گراف، یال‌ها دارای جهت مشخصی هستند. به عبارت دیگر، ارتباط بین دو راس در گراف جهت‌دار به صورت یک جهت مشخص از راس مبدا به راس مقصد است. مورد بعد گراف وزن‌دار (Weighted Graph) است. در این نوع گراف، هر یال دارای یک وزن یا ارزش است. وزن می‌تواند نشان‌دهنده فاصله بین رئوس، هزینه یا هر معیار دیگر مرتبط با ارتباط بین رئوس باشد. مورد بعدی گراف بدون دور (Acyclic Graph) است. در این نوع گراف، هیچ مسیری وجود ندارد که از یک راس به خودش بازگردد. به عبارت دیگر، در گراف بدون دور، نمی‌توان از یک راس شروع کرده و به صورت مکرر از یالی که به همان راس برمی‌گردد، عبور کرد. گراف متصل‌شده (Connected Graph) نوع دیگری است که بین هر دو راس، حداقل یک مسیر وجود دارد. به عبارت دیگر، می‌توان از هر رأس به هر راس دیگری در گراف همبند دسترسی داشت.

نوع بعد، گراف جزیی (Partial Graph) است. در این نوع گراف، تعدادی رئوس و یال‌ها از گراف حذف شده‌اند، به طوری که شبکه‌ای کوچک‌تر از گراف اصلی باقی می‌ماند. در گراف دوار (Cyclic Graph) یک مسیر وجود دارد که از یک راس شروع شده و به همان راس برمی‌گردد. به عبارت دیگر، در گراف دوره‌دار، می‌توان مسیری را پیدا کرد که شامل یال‌هایی است که به صورت مکرر به راس اول بازمی‌گردد. این تقسیم‌بندی‌ها تنها برخی از انواع موجود در نظریه گراف را شامل می‌شوند و هر نوع گراف ممکن است ویژگی‌ها و استفاده‌های موجودی داشته باشد. توجه به نوع گراف مورد نظر بسیار مهم است، زیرا این نوع تعیین‌کننده‌ای برای رفتار و خواص مرتبط با آن گراف است. اکنون اجازه دهید هریک از گراف‌ها را با جزییات بیشتری مورد بررسی قرار دهیم.

گراف غیر متصل (Disconnected Graph)

گراف غیر متصل یک نوع گراف است که شامل دو یا بیشتر مولفه متصل نیست. به عبارت دیگر، در گراف غیر متصل، حداقل دو راس یا بیشتر وجود دارند که بین آن‌ها هیچ یالی وجود ندارد و ارتباطی بین آن‌ها برقرار نیست. به عنوان مثال ساده، فرض کنید دو سه راس در یک گراف وجود داشته باشد و بین آن‌ها یالی وجود نداشته باشد. در این صورت، گراف به دو مولفه غیر متصل تقسیم می‌شود، به این معنی که راس‌های مولفه اول نمی‌توانند به راس‌های مولفه دوم دسترسی داشته باشند. گراف غیر متصل در برخی مسائل و کاربردها به دلیل عدم ارتباط بین بخش‌های مختلف مورد استفاده قرار گیرد. علاوه بر این، تحلیل و مدلسازی گراف غیر متصل می‌تواند به تجزیه و تحلیل بخش‌های مختلف یک سیستم کمک کند و به ما در فهمندگی و ارتباط بین اجزا کمک می‌کند.

گراف متصل (Connected Graph)

گراف متصل (Connected Graph) یک نوع گراف است که بین هر دو رأس در آن حداقل یک مسیر وجود دارد. به عبارت دیگر، از هر راس به هر راس دیگری در گراف متصل می‌توان به صورت مستقیم یا غیرمستقیم دسترسی داشت. این به این معنی است که با استفاده از یال‌های موجود در گراف، می‌توان بین هر دو رأس، یک مسیر را پیدا کرد. یک گراف متصل ممکن است شامل چندین جز (component) متصل باشد. هر جز، یک زیرگراف متصل است که بین هر دو رأس در آن حداقل یک مسیر وجود دارد. با اتصال هر دو جز متصل به یک یال، می‌توان گراف متصل کلی را به دست آورد. مفهوم گراف متصل در مسایل مختلف بسیار مهم است. به عنوان مثال، در شبکه‌ها، برقراری ارتباط بین تمام عناصر شبکه از اهمیت بالایی برخوردار است و گراف متصل معمولا نشان‌دهنده قابلیت ارتباط بین تمام اجزا است. در الگوریتم‌ها، برای برخی از مسائل مانند جست‌وجوی مسیر کوتاه، گراف متصل باید تضمین شود تا بتوان به صورت صحیح از یک راس به راس دیگر حرکت کرد. بنابراین، گراف متصل مفهومی مهم در نظریه گراف است که به ما اجازه می‌دهد رابطه و ارتباطات بین اجزا مختلف گراف را به صورت کامل بررسی کنیم.

گراف درختی (Tree Graph)

گراف درختی (Tree Graph) یک نوع خاص از گراف است که به صورت سلسله‌مراتبی و بدون دوری تشکیل می‌شود. در گراف درختی، یک راس خاص به نام راس ریشه (Root) تعیین می‌شود و از آن به سایر رئوس دسترسی وجود دارد. همچنین، هر راس به صورت مستقیم یا غیر مستقیم، با دقیقا یک راس دیگر در گراف درختی متصل است. ویژگی مهم دیگر در گراف درختی، وجود مسیر یکتا بین هر دو راس است. به عبارت دیگر، بین هر دو راس در گراف درختی فقط یک مسیر وجود دارد. این ویژگی یکی از مهم‌ترین خصوصیات گراف درختی است که آن را از سایر انواع گراف‌ها متمایز می‌کند. گراف درختی معمولا به عنوان یک ساختار سلسله‌مراتبی برای نمایش روابط میان داده‌ها استفاده می‌شود. راس ریشه به عنوان راس بالاترین سطح، رئوس فرزندان آن به عنوان رئوس سطح پایین‌تر و یال‌ها به عنوان ارتباطات بین رئوس استفاده می‌شوند. به طور معمول، گراف درختی برای نمایش سلسله مراتب ساختارهای مانند سلسله‌مراتب جنسیتی، سلسله‌مراتب سازمانی یا نمایش دسته‌بندی‌ها و زیردسته‌ها استفاده می‌شود. مهم‌ترین ویژگی‌های گراف درختی شامل عدم وجود دور، تنها وجود یک مسیر بین هر دو راس، و وجود راس ریشه است. این ویژگی‌ها باعث می‌شوند گراف درختی به عنوان یک ساختار ساده، قابل مدیریت و قابل استفاده در موارد مختلف مورد توجه قرار گیرد.

گراف بدون ‌جهت (Undirected Graph)

گراف بی‌جهت یک نوع گراف است که در آن یال‌ها بی‌جهت هستند، به این معنی که بین دو راس A و B یک یال وجود دارد که می‌توان از هر دو جهت بین A و B حرکت کرد. به عبارت دیگر، رابطه بین رئوس در این گراف‌ها دوطرفه است و جهت حرکت در امتداد یال‌ها مهم نیست. در گراف بی‌جهت، هر یال معادل با یک رابطه دوطرفه بین دو راس است، به طوری که اگر بین دو راس A و B یک یال وجود داشته باشد، می‌توان از راس A به راس B حرکت کرد و برعکس، از راس B به راس A نیز می‌توان حرکت کرد. در گراف بی‌جهت، مفهوم درجه رئوس نیز به کار می‌رود. درجه راس نشان می‌دهد که یک راس با چند یال به رئوس دیگر متصل است. در گراف بی‌جهت، درجه رئوس برابر با تعداد یال‌های متصل به آن راس است. گراف بی‌جهت می‌تواند شامل دورها و جزیره‌ها باشد. دور در یک گراف بی‌جهت مسیری است که از یک راس شروع شده و به همان راس بازگشت می‌یابد. جزیره‌ها مجموعه‌ای از رئوس است که بین هر دو راس در آن مسیری وجود ندارد. گراف بی‌جهت در مسائل مختلفی از جمله شبکه‌های اجتماعی، شبکه‌های مخابراتی و مسائل مسیریابی استفاده می‌شود. ویژگی بی‌جهت بودن یال‌ها باعث می‌شود که تحلیل و مدلسازی ارتباطات و روابط دوطرفه بین اجزای سیستم را ممکن سازد.

گراف جهت‌دار (Directed Graph)

گراف جهت‌دار یک نوع گراف است که در آن یال‌ها دارای جهت مشخصی هستند. به عبارت دیگر، بین دو راس A و B در یک گراف جهت‌دار، یک یال وجود داشته باشد، حرکت فقط از راس A به راس B ممکن است و جهت حرکت از اهمیت بالایی برخوردار است. در گراف جهت‌دار، یال‌ها به صورت جفت‌ مرتبه‌ای از دو راس نمایش داده می‌شوند. اگر بین دو راس A و B یک یال جهت‌دار وجود داشته باشد، آنگاه راس A راس مبدأ (source) نامیده می‌شود و راس B راس مقصد (destination) نامیده می‌شود.

در گراف جهت‌دار، مفهوم درجه رئوس به دو صورت متمایز است. درجه ورودی (in-degree) یک راس، تعداد یال‌هایی است که به آن راس وارد می‌شوند و درجه خروجی (out-degree) یک راس، تعداد یال‌هایی است که از آن راس خارج می‌شوند. گراف جهت‌دار می‌تواند شامل دورها (cycles) باشد که مسیری است که از یک راس شروع شده و بعد از طی کردن چند راس به همان راس بازگشت می‌یابد. همچنین، می‌تواند شامل جزیره‌ها (islands) باشد که مجموعه‌ای از رئوس است که بین هر دو راس در آن مسیری وجود ندارد. گراف جهت‌دار در مسائلی که نیاز به نشان دادن جریان، وابستگی‌ها، روابط توالی و رویدادها داریم، استفاده می‌شود. به عنوان مثال، در شبکه‌های جاده‌ای، شبکه‌های مخابراتی، الگوریتم‌های جستجو و مسائل برنامه‌ریزی زمانی، گراف جهت‌دار مفید است.

گراف ساده (Simple Graph)

گراف ساده یک نوع گراف است که بیش از یک یال بین هر دو راس وجود ندارد و تکراری نیست. به عبارت دیگر، هر دو راس در یک گراف ساده حداکثر یک بار با یکدیگر متصل هستند. در گراف ساده، هر یال معادل با یک رابطه بین دو راس است و هیچ یالی تکراری نیست. این حرف بدان معنا است که بین هر دو راس، فقط یک یال وجود دارد و امکان وجود حلقه (دور) در گراف ساده نیست. گراف ساده مفید در بسیاری از مسائل و کاربردهاست، از جمله تحلیل شبکه‌ها، مسایل ترافیک، شبکه‌های اجتماعی، مسائل مسیریابی و الگوریتم‌های گرافی. این نوع گراف به دلیل سادگی ساختار و عدم وجود یال‌های تکراری، تحلیل و مدلسازی آن را آسانتر می‌کند و مفاهیمی مانند درجه رئوس و مسیرها به راحتی قابل محاسبه و استنتاج هستند.

گراف چندگانه (Multigraph)

گراف چندگانه یک نوع گراف است که در آن اجازه داده می‌شود بیش از یک یال بین هر دو راس وجود داشته باشد. به عبارت دیگر، در گراف چندگانه، بین دو راس می‌تواند یک یا چند یال وجود داشته باشد و این یال‌ها ممکن است تکراری باشند. در گراف چندگانه، هر یال معادل با یک رابطه بین دو راس است و می‌تواند تکرار شود. به عبارت دیگر، بین هر دو راس، بیش از یک یال می‌تواند وجود داشته باشد. این مفهوم چندگانگی یال‌ها، به معنای وجود چندین ارتباط مستقل بین دو راس است. گراف چندگانه در برخی مسائل و کاربردها مفید است، به ویژه زمانی که نیاز به نشان دادن روابط متعدد و متنوع بین اجزا وجود دارد. به عنوان مثال، در شبکه‌های مخابراتی که مسیر‌های مختلفی بین دو نقطه وجود دارد، گراف چندگانه می‌تواند استفاده شود. همچنین، در برخی مسایل مسیریابی و ارتباطات شبکه، گراف چندگانه به دلیل قابلیت نمایش روابط چندگانه بین اجزا، مورد استفاده قرار می‌گیرد.

گراف وزن‌دار (Weighted Graph)

گراف وزن‌دار یک نوع گراف است که در آن به هر یال یک وزن یا ارزش نسبت داده می‌شود. به عبارت دیگر، هر یال در گراف وزن‌دار با یک عدد یا مقدار عددی مشخص مرتبط است که به عنوان وزن یال شناخته می‌شود. وزن‌ها می‌توانند مثبت، منفی یا صفر باشند و با توجه به مساله و کاربرد مورد استفاده، معنای خاصی را نمایان می‌سازند. معمولا وزن‌ها معرف اهمیت، فاصله، هزینه یا قیمت بین دو راس در گراف هستند.

در گراف وزن‌دار، وزن هر یال می‌تواند برای محاسبه‌ی معیارهای مختلفی مانند کوتاه‌ترین مسیرها، مسئله‌های جستجو، الگوریتم‌های بهینه‌سازی و تحلیل شبکه‌ها استفاده شود. با استفاده از وزن‌ها، می‌توان به صورت دقیق‌تر و شخصی‌تر به مسایل مورد بررسی نگریست و تصمیم‌گیری‌ها را براساس ارزش‌ها و اولویت‌های مشخص ترتیب بندی کرد. مثال‌هایی از کاربردهای گراف وزن‌دار شامل شبکه‌های جاده‌ای با مسافت‌های مختلف بین شهرها، شبکه‌های اجتماعی با وزن‌دهی به روابط و شبکه‌های مخابراتی با وزن‌دهی به ظرفیت است.

بخوانید : پردازش زبان طبیعی (NLP) چگونه از محاسبات شناختی استفاده می‌کند؟