رأسهای مجاور در گراف: شناخت همسایهها در ساختارهای شبکهای
تعریف پایه و نمادگذاری رأسهای مجاور
در یک گراف بدون جهت G = (V, E) که V مجموعهٔ رأسها (گرهها) و E مجموعهٔ یالها (پیوندها) است، دو رأس مانند u و v را مجاور گویند اگر یالی مستقیم بین آنها موجود باشد. این رابطه را با نماد u \sim v نشان میدهند. به عبارت دیگر، رأس u همسایهٔ رأس v است اگر فاصلهٔ بین آن دو در گراف دقیقاً یک یال باشد.
برای درک بهتر، یک گراف با 5 رأس به نامهای A, B, C, D, E را در نظر بگیرید که یالهای A-B، B-C، C-D و D-E را دارد. در این گراف، رأس B با A و C مجاور است، اما با D مجاور نیست زیرا بین B و D یال مستقیمی وجود ندارد.
انواع گراف و تأثیر بر مفهوم مجاورت
مفهوم رأسهای مجاور در انواع مختلف گراف به شکلهای متفاوتی ظاهر میشود. در جدول زیر مهمترین انواع گراف و ویژگی مجاورت در آنها مقایسه شده است:
| نوع گراف | شرط مجاورت | مثال |
|---|---|---|
| گراف بدون جهت | دو رأس با یک یال به هم وصل شدهاند (رابطه متقارن) | اگر u-v یال داشته باشد، u و v مجاورند |
| گراف جهتدار | وجود یال از u به v؛ مجاورت معمولاً نامتقارن است | در یال u \to v، v مجاور u است ولی لزوماً برعکس نه |
| گراف کامل1 | هر دو رأس متمایزی با هم مجاورند | در K_4 هر یک از 4 رأس با 3 رأس دیگر مجاور است |
| گراف دو بخشی2 | مجاورت فقط بین رأسهای دو بخش متفاوت رخ میدهد | در گراف دو بخشی کامل K_{2,3} هر رأس بخش اول با همهٔ رأسهای بخش دوم مجاور است |
کاربرد عملی: شبکهٔ اجتماعی و مسیریابی شهری
فرض کنید میخواهید شبکهٔ دوستی در یک کلاس 30 نفره را مدل کنید. هر دانشآموز یک رأس است و اگر دو نفر با هم دوست باشند، یک یال بین آنها رسم میشود. در این گراف، رأسهای مجاور همان دوستهای مستقیم هر فرد هستند. اگر بخواهید پیامی را از دانشآموز A به D برسانید و فقط اجازه دارید پیام را به دوستان مستقیم بدهید، اولین قدم پیدا کردن همسایههای A است. مفهوم مجاورت در اینجا پایهٔ الگوریتمهای پخش اطلاعرسانی در شبکههای اجتماعی است.
در مسیریابی شهری، تقاطعها رأس و خیابانها یال هستند. دو تقاطع مجاور یعنی مستقیماً با یک خیابان به هم متصلاند. سامانهٔ مسیریاب مانند نشانگرهای گوگل برای یافتن کوتاهترین مسیر، ابتدا همسایههای نقطهٔ شروع را بررسی میکند. بنابراین درک رأسهای مجاور برای نوشتن الگوریتم جستجوی اول سطح3 بسیار ضروری است.
چالشهای مفهومی
پاسخ: در گراف ساده (بدون حلقه)، خیر. حلقه4 یالی است که یک رأس را به خودش متصل میکند. در گرافهایی که حلقه مجاز است، برخی تعاریف رأس را با خودش مجاور میدانند اما در اکثر متون مقدماتی، مجاورت فقط برای دو رأس متمایز تعریف میشود.
پاسخ: بله، در گراف چندگانه (شبهگراف) نیز وجود حداقل یک یال مستقیم برای مجاورت کافی است. تعداد یالها بر اصل مجاورت تأثیر نمیگذارد ولی بر مفهوم «تعدد یال» اثر دارد.
پاسخ: کاملاً صحیح است. اگر دو رأس مجاور باشند، حتماً در یک مؤلفهٔ همبندی قرار میگیرند زیرا یال مستقیم بین آنها یک مسیر به طول 1 ایجاد میکند. اما عکس این گزاره درست نیست: دو رأس در یک مؤلفه میتوانند غیرمجاور باشند (مثلاً با فاصلهٔ بیشتر از یک یال).
بازنمایی ریاضی و ماتریس مجاورت
برای ذخیرهسازی اطلاعات مجاورت در کامپیوتر، از ماتریس مجاورت7 استفاده میشود. برای گراف با n رأس، ماتریس A به ابعاد n \times n تعریف میشود به طوری که:
برای مثال، گراف مسیری با سه رأس 1-2-3 دارای ماتریس مجاورت زیر است (سطر و ستون اول مربوط به رأس 1، دومی 2 و سومی 3):
توان ماتریس مجاورت، اطلاعات جالبی دربارهٔ تعداد مسیرهای با طول مشخص بین رأسها میدهد. برای نمونه، درجهٔ هر رأس از مجموع سطر متناظر در ماتریس مجاورت به دست میآید: $\deg(v_i) = \sum_{j=1}^{n} A_{ij}$.
رأسهای مجاور یا همسایه، پایهترین مفهوم در نظریهٔ گراف برای نشان دادن ارتباط مستقیم بین دو گره هستند. این مفهوم در گرافهای بدون جهت، جهتدار، کامل و دو بخشی با اندکی تغییر تعریف میشود. آشنایی با مجاورت برای درک درجهٔ رأس، ماتریس مجاورت، الگوریتمهای جستجو (مانند BFS) و مسائل مسیریابی ضروری است. با تسلط بر این مفهوم، میتوان مدلسازی بسیاری از پدیدههای دنیای واقعی از شبکههای اجتماعی گرفته تا مدارهای الکتریکی را سادهتر انجام داد.
پاورقی
1 گراف کامل (Complete Graph): گرافی که در آن هر دو رأس متمایزی دقیقاً با یک یال به هم متصل شدهاند و با K_n نشان داده میشود.2 گراف دو بخشی (Bipartite Graph): گرافی که مجموعه رأسهای آن را میتوان به دو بخش مجزا افراز کرد به طوری که هر یال یک رأس از بخش اول را به رأس از بخش دوم متصل کند.
3 جستجوی اول سطح (Breadth-First Search - BFS): الگوریتمی برای پیمایش یا جستجو در گراف که از یک رأس شروع کرده و ابتدا همهٔ همسایههای آن را بررسی میکند.
4 حلقه (Loop): یالی که یک رأس را به خودش متصل میکند.
5 یال چندگانه (Multiple Edge): دو یا چند یال که بین یک جفت رأس قرار میگیرند.
6 مؤلفهٔ همبندی (Connected Component): زیرگرافی که هر دو رأس در آن با یک مسیر به هم متصلاند و به بقیهٔ گراف متصل نیست.
7 ماتریس مجاورت (Adjacency Matrix): ماتریس مربعی دودویی که درایههای آن نشاندهندهٔ مجاورت بین رأسهای یک گراف است.
