نمودار گراف: نمایش تصویری ساختار گرهها و یالها
رأسها و یالها: اجزای اصلی یک گراف
یک گراف از دو مجموعه تشکیل میشود: مجموعهٔ رأسها (نقاط یا گرهها) و مجموعهٔ یالها (ارتباطها یا پلها). هر یال دو رأس را به هم متصل میکند. در زندگی روزمره، میتوان ایستگاههای مترو را بهعنوان رأس و خطوط ارتباطی میان آنها را بهعنوان یال در نظر گرفت. اگر جهت حرکت مشخص باشد (مثلاً یک خیابان یکطرفه)، از گراف جهتدار استفاده میکنیم. در غیر این صورت، گراف بدون جهت خواهیم داشت.
به عنوان مثال، در یک گراف با 5 رأس، بیشترین تعداد یال بدون جهت برابر $ \frac{5 \times 4}{2} = 10 $ است. برای گراف جهتدار، این مقدار دو برابر میشود زیرا هر جفت رأس امکان دو یال (در دو جهت) را دارد.
گراف جهتدار در برابر گراف بدون جهت: مقایسه در جدول
| ویژگی | گراف بدون جهت | گراف جهتدار |
|---|---|---|
| نمایش یال | خط بدون پیکان | خط با پیکان (نشاندهنده جهت) |
| تقارن ارتباط | همیشه متقارن (اگر $u$ به $v$ متصل است، برعکس نیز صادق است) | میتواند نامتقارن باشد |
| مثال واقعی | شبکه دوستان فیسبوک (رابطه دوطرفه) | دنبال کردن در اینستاگرام (یکطرفه) |
کاربرد عملی: مسیریابی و شبکههای اجتماعی
سیستمهای مسیریابی مانند نشان (نقشه) از گراف برای یافتن کوتاهترین مسیر استفاده میکنند. تقاطعها رأس و خیابانها یال هستند. الگوریتم دایجسترا4 با استفاده از وزن یالها (طول مسیر) بهترین مسیر را پیدا میکند. در شبکههای اجتماعی، گراف جهتدار به ما نشان میدهد چه کسی چه کسی را دنبال میکند و مفاهیمی مانند درجه ورودی و درجه خروجی اهمیت پیدا میکنند.
مثال عینی: در یک کلاس 6 نفری، اگر هر دانشآموز دقیقاً با 2 نفر دیگر دوست باشد (گراف دوستی بدون جهت)، مجموع درجهها برابر $6 \times 2 = 12$ خواهد بود. در نتیجه تعداد یالهای دوستی برابر $12 / 2 = 6$ است.
چالشهای مفهومی در نمایش تصویری گراف
پاسخ: نمایش تصویری گراف فقط توپولوژی (نحوه ارتباط) را نشان میدهد، نه موقعیت هندسی. بنابراین میتوان رأسها را جابهجا کرد بدون آنکه یالها قطع شوند یا ارتباط تغییر کند. دو گراف که با تغییر مکان رأسها به هم تبدیل شوند، همریخت6 نامیده میشوند.
پاسخ: در گراف وزندار، هر یال یک عدد (مانند طول، هزینه یا زمان) به خود میگیرد. نمایش تصویری آن با نوشتن عدد روی یال انجام میشود. در مقابل گراف بدون وزن فقط وجود یا عدم وجود یال را نشان میدهد.
پاسخ: خیر. گرافهایی که بدون تقاطع یال (به جز در رأس) قابل رسم باشند، مسطح7 نامیده میشوند. گراف کامل $K_5$ (پنج رأس که همه به هم متصلاند) مسطح نیست و همیشه در هر نمایشی تقاطع خواهد داشت.
پرسشهای متداول (خلاصه)
- آیا گراف میتواند شامل حلقه باشد؟ بله، حلقه9 یالی است که یک رأس را به خودش متصل میکند.
- چگونه یک گراف را ذخیره کنیم؟ با ماتریس مجاورت10 یا لیست مجاورت.
پاورقی
1 گراف جهتدار (Directed Graph): گرافی که هر یال آن دارای جهت بوده و رابطهٔ نامتقارن را نشان میدهد.
2 گراف بدون جهت (Undirected Graph): گرافی که یالها بدون جهت بوده و رابطهای متقارن را نمایش میدهند.
3 گراف ساده (Simple Graph): گرافی بدون حلقه و یال موازی (چند یال بین یک جفت رأس).
4 الگوریتم دایجسترا (Dijkstra's Algorithm): روشی برای یافتن کوتاهترین مسیر از یک مبدأ به تمام رأسها در گراف با وزن نامنفی.
5 لم دست دادن (Handshaking Lemma): قضیهای که میگوید مجموع درجهٔ همهٔ رأسهای یک گراف برابر دو برابر تعداد یالها است.
6 همریخت (Isomorphic): دو گراف که ساختار ارتباطی یکسانی داشته باشند و تنها در نامگذاری یا موقعیت رأسها متفاوت باشند.
7 گراف مسطح (Planar Graph): گرافی که بتوان آن را روی صفحه بدون تقاطع یالها (به جز در رأس) رسم کرد.
8 درخت (Tree): گراف همبند بدون دور.
9 حلقه (Loop): یالی که یک رأس را به خودش متصل میکند.
10 ماتریس مجاورت (Adjacency Matrix): جدولی دوبعدی که در آن سطر $i$ و ستون $j$ نشاندهندهٔ وجود یا وزن یال بین رأس $i$ و $j$ است.