رأس گراف: نقطهای از گراف
رأس چیست و چه نقشی در گراف دارد؟
در نظریهی گراف1، یک گراف از دو مجموعهی اصلی ساخته میشود: مجموعهی رأسها (Vertices) و مجموعهی یالها2 (Edges). هر رأس معمولاً با یک نقطه یا دایرهی کوچک نمایش داده میشود و نشاندهندهی یک «چیز» یا «موقعیت» است. برای مثال، در نقشهی متروی یک شهر، ایستگاهها نقش رأس را دارند و خطوط قطار، یالها هستند.
رأسها میتوانند دارای برچسب (Label) باشند تا شناسایی آنها آسان شود. برای نمونه، در گراف شبکههای اجتماعی، هر کاربر یک رأس است و نام او برچسب آن رأس به شمار میرود. تعداد رأسهای یک گراف را «مرتبه» یا «ساختار» آن گراف مینامند و معمولاً با حرف $n$ نشان داده میشود.
مثال عینی: فرض کنید سه شهر تهران، اصفهان و شیراز را به عنوان رأس در نظر بگیریم. اگر بین تهران و اصفهان یک یال (جاده) وجود داشته باشد، میگوییم این دو رأس با یک یال به هم متصل شدهاند. در این گراف ساده، هر رأس نمایندهی یک شهر است و هیچ رأس دیگری در میان نیست.
انواع رأس بر اساس نوع گراف
بسته به این که گراف جهتدار، بدون جهت، یا دارای حلقه3 باشد، رأسها رفتار متفاوتی از خود نشان میدهند. در ادامه مهمترین انواع رأس را با هم مرور میکنیم.
| نوع گراف | ویژگی رأس | مثال |
|---|---|---|
| گراف بدون جهت | رأسها از طریق یالهای دوطرفه به هم متصل میشوند. | دو دوست در شبکههای اجتماعی |
| گراف جهتدار | هر یال دارای جهت است (از یک رأس به رأس دیگر). | دنبال کردن صفحه در اینستاگرام |
| گراف با حلقه | رأس میتواند به خودش متصل شود. | عملی که یک شخص برای خودش انجام میدهد |
| گراف ساده | بین هر دو رأس حداکثر یک یال وجود دارد و هیچ حلقهای نیست. | نقشه پروازهای مستقیم بین شهرها |
درجه یا مرتبهی رأس: قدم اول در تحلیل گراف
یکی از مهمترین ویژگیهای هر رأس، «درجه» (Degree) آن است. درجهی یک رأس برابر است با تعداد یالهایی که به آن رأس متصل میشوند. در گراف بدون جهت، هر یال به افزایش درجهی هر دو رأس خود کمک میکند. در گراف جهتدار، دو نوع درجه تعریف میشود: درجهی ورودی (تعداد یالهای وارد شده به رأس) و درجهی خروجی (تعداد یالهای خارج شده از رأس).
همچنین در گراف جهتدار: $\deg^+(v)$ (خروجی) و $\deg^-(v)$ (ورودی) و داریم: $\deg(v) = \deg^+(v) + \deg^-(v)$.
اگر درجهی یک رأس برابر صفر باشد، آن را «رأس تنها» یا «منزوی» مینامیم. اگر درجهی یک رأس برابر یک باشد، آن را «برگ» میگویند که در درختها4 بسیار رایج است. برای نمونه، در یک درخت شجرهنامهی ساده، افرادی که فرزندی ندارند، برگهای آن درخت هستند.
کاربردهای عملی رأس در زندگی روزمره
مفهوم رأس تنها به ریاضیات نظری محدود نمیشود، بلکه در بسیاری از زمینههای علمی و فنی نقش کلیدی دارد. در ادامه به چند کاربرد عینی اشاره میکنیم:
شبکههای کامپیوتری: هر رأس میتواند یک کامپیوتر یا یک روتر باشد. یالها نشاندهندهی اتصالات فیزیکی یا بیسیم بین آنها هستند. با تحلیل درجهی رأسها، میتوان نقاط بحرانی شبکه را شناسایی کرد.
شیمی و مولکولها: در شیمی، اتمها نقش رأس و پیوندهای شیمیایی نقش یال را بازی میکنند. برای نمونه، مولکول متان $CH_4$ دارای یک رأس کربن و چهار رأس هیدروژن است که همگی به کربن متصل شدهاند.
مسیریابی و نقشه: نرمافزارهای مسیریابی مانند نشانها و گوگل مپ، تقاطعها را به صورت رأس و خیابانها را به صورت یال مدل میکنند. کوتاهترین مسیر بین دو رأس با استفاده از الگوریتمهایی مانند دیکسترا5 محاسبه میشود.
چالشهای مفهومی
بله. اگر گراف «چندگانه» (Multigraph) باشد، اجازهی وجود چند یال موازی بین یک جفت رأس وجود دارد. برای نمونه، دو شهر که با دو جادهی متفاوت به هم متصل شدهاند.
رأس نشاندهندهی یک موجودیت یا نقطه است، در حالی که یال ارتباط بین دو رأس را نمایش میدهد. بدون رأس، گراف وجود ندارد؛ بدون یال، گرافی با رأسهای تنها خواهیم داشت که «گراف تهی» نامیده میشود.
اگر مسیری (دنبالهای از یالها) بین آن دو رأس وجود داشته باشد، میگوییم آن دو رأس در یک «همبندی» (Component) قرار دارند. در گراف همبند، بین هر جفت رأس حداقل یک مسیر وجود دارد.
جمعبندی
پاورقی
1 گراف (Graph): ساختاری ریاضی متشکل از رأسها و یالها که روابط بین اشیاء را مدل میکند.
2 یال (Edge): ارتباط یا پیوند بین دو رأس در یک گراف.
3 حلقه (Loop): یالی که یک رأس را به خودش متصل میکند.
4 درخت (Tree): گراف همبند بدون هیچ دوری که در آن هر دو رأس با دقیقاً یک مسیر به هم وصل میشوند.
5 الگوریتم دیکسترا (Dijkstra's Algorithm): روشی برای یافتن کوتاهترین مسیر بین دو رأس در گراف وزنی بدون جهت منفی.