گراف: ساختاری شامل مجموعه‌ای از رأس‌ها و یال‌ها.

گراف: ساختاری برای نمایش ارتباطات پنهان در داده‌ها

رأس و یال: اجزای اصلی گراف

هر گراف از دو بخش مهم ساخته شده است: رأس¹ و یال². تصور کنید نقشه متروی یک شهر را نگاه می‌کنید. ایستگاه‌ها همان رأس‌ها هستند و خطوط آهنی که ایستگاه‌ها را به هم متصل می‌کنند، یال‌ها محسوب می‌شوند. در گراف، رأس‌ها معمولاً با دایره‌های کوچک و یال‌ها با خطوط راست یا منحنی نمایش داده می‌شوند. به مجموعه همه رأس‌ها، مجموعه رأس‌ها (V) و به مجموعه همه یال‌ها، مجموعه یال‌ها (E) می‌گوییم. در نتیجه یک گراف را به صورت $G = (V, E)$ نشان می‌دهیم.

مثال علمی ساده: فرض کنید کلاسی با $5$ دانش‌آموز دارید. اگر هر دانش‌آموز را یک رأس در نظر بگیریم، و برای هر دو نفری که با هم دوست هستند یک یال رسم کنیم، به یک گراف دوستی می‌رسیم. تعداد رأس‌ها $n = 5$ است و یال‌ها نشان‌دهنده روابط اجتماعی هستند. اگر همه با هم دوست باشند، یک گراف کامل³ خواهیم داشت که در آن هر دو رأس با یک یال به هم وصل شده‌اند. تعداد یال‌ها در گراف کامل با $ \frac{n(n-1)}{2} $ محاسبه می‌شود. برای $n = 5$، تعداد یال‌ها برابر $ \frac{5 \times 4}{2} = 10$ خواهد بود.

انواع گراف: جهت‌دار، بی‌جهت و وزن‌دار

گراف‌ها بر اساس جهت یال‌ها به دو دسته اصلی تقسیم می‌شوند. اگر یال‌ها جهت نداشته باشند (یعنی رابطه بین دو رأس دوطرفه باشد)، گراف بی‌جهت⁴ نامیده می‌شود. مثال دوستی در شبکه اجتماعی، یک گراف بی‌جهت است. اما اگر یال‌ها دارای جهت باشند (مثل دنبال کردن در اینستاگرام که ممکن است یک طرفه باشد)، به آن گراف جهت‌دار⁵ می‌گوییم. در گراف جهت‌دار، یال‌ها با پیکان نشان داده می‌شوند.

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

کاربرد عملی: یافتن کوتاه‌ترین مسیر در زندگی روزمره

یکی از جذاب‌ترین کاربردهای گراف، حل مسئله کوتاه‌ترین مسیر⁷ است. فرض کنید می‌خواهید از خانه به مدرسه بروید و چندین خیابان مختلف وجود دارد. هر تقاطع یک رأس و هر خیابان یک یال با وزن برابر طول آن خیابان است. با استفاده از الگوریتم دیکسترا⁸ می‌توانید کوتاه‌ترین مسیر را پیدا کنید. این الگوریٹم بارها در دستگاه‌های مسیریاب خودرو و گوگل مپ استفاده می‌شود.

مثال ملموس: تصور کنید چهار مکان A، B، C و D داریم. یال AB با وزن $5$، یال AC با وزن $2$، یال BC با وزن $1$، یال BD با وزن $7$ و یال CD با وزن $3$. کوتاه‌ترین مسیر از A به D از مسیر A → C → B → D نیست (چون مجموع وزن‌ها $2+1+7=10$) بلکه مسیر A → C → D با مجموع $2+3=5$ کوتاه‌تر است. این محاسبات ساده نشان می‌دهد که گراف چگونه به بهینه‌سازی کمک می‌کند.

چالش‌های مفهومی در درک گراف

پاورقی

¹ رأس (Vertex): نقطه یا گره در گراف که نشان‌دهنده یک شیء یا موجودیت است.
² یال (Edge): خط یا ارتباط بین دو رأس که نشان‌دهنده رابطه یا پیوند است.
³ گراف کامل (Complete Graph): گرافی که در آن هر دو رأس متمایز با یک یال به هم متصل شده‌اند.
⁴ گراف بی‌جهت (Undirected Graph): گرافی که یال‌های آن جهت ندارند و رابطه بین رأس‌ها متقارن است.
⁵ گراف جهت‌دار (Directed Graph): گرافی که هر یال آن دارای جهت مشخصی است و با پیکان نشان داده می‌شود.
⁶ گراف وزن‌دار (Weighted Graph): گرافی که به هر یال آن یک مقدار عددی (وزن) مانند فاصله یا هزینه نسبت داده شده است.
⁷ کوتاه‌ترین مسیر (Shortest Path): مسئله‌ی یافتن مسیری بین دو رأس که مجموع وزن یال‌های آن حداقل باشد.
⁸ الگوریتم دیکسترا (Dijkstra's Algorithm): الگوریتمی برای یافتن کوتاه‌ترین مسیر از یک رأس مبدأ به سایر رأس‌ها در گراف‌های وزن‌دار با وزن‌های غیرمنفی.
⁹ درخت (Tree): گراف همبند بی‌جهتی که هیچ دور (حلقه بسته) نداشته باشد.
¹⁰ دوره (Cycle): مسیری بسته در گراف که رأس شروع و پایان آن یکی بوده و هیچ رأس یا یالی جز رأس شروع تکرار نشود.
¹¹ مسئله فروشنده دوره‌گرد (Traveling Salesman Problem): مسئله یافتن کوتاه‌ترین مسیری که از تمام رأس‌های یک گراف عبور کرده و به نقطه شروع بازگردد.