همسایگی باز رأس در گراف: مفاهیم و کاربردها
تعریف همسایگی باز و تفاوت آن با همسایگی بسته
در نظریهٔ گراف1، یک گراف از دو چیز اصلی ساخته میشود: رأسها2 (که گاهی گره هم نامیده میشوند) و یالها3 (که ارتباط بین رأسها را نشان میدهند). اگر دو رأس با یک یال به هم متصل شده باشند، میگوییم آن دو رأس مجاور یا همسایه هستند.
همسایگی باز یک رأس مانند $v$، مجموعهٔ همهٔ رأسهایی است که با $v$ مجاورند، اما خود $v$ در این مجموعه عضو نیست. به عبارت دیگر، اگر $N(v)$ را نماد همسایگی باز در نظر بگیریم، داریم:
در این فرمول، $V(G)$ مجموعهٔ همهٔ رأسها و $E(G)$ مجموعهٔ یالهای گراف است. برای درک بهتر، به یک گراف ساده شامل $4$ رأس به نامهای $A, B, C, D$ توجه کنید. فرض کنید یالها به این صورت هستند: $A-B$، $A-C$ و $B-C$. در این گراف، همسایگی باز رأس $A$ برابر است با $\{B, C\}$ زیرا فقط این دو رأس با $A$ یال دارند و خود $A$ در مجموعه نیست.
در مقابل، همسایگی بسته که با $N[v]$ نشان داده میشود، خود رأس را نیز شامل میشود: $N[v] = N(v) \cup \{v\}$. در مثال بالا، همسایگی بستهٔ $A$ برابر است با $\{A, B, C\}$. تفاوت اصلی در حضور یا عدم حضور خود رأس در مجموعه است.
| ویژگی | همسایگی باز ($N(v)$) | همسایگی بسته ($N[v]$) |
|---|---|---|
| اعضای مجموعه | فقط رأسهای مجاور | رأسهای مجاور + خود رأس |
| تعداد اعضا در گراف کامل $K_n$ | $n-1$ | $n$ |
| کاربرد معمول | تحلیل تأثیر همسایهها (بدون تأثیر خود گره) | تحلیل تأثیر گره به همراه همسایهها |
مثال عینی از همسایگی باز در شبکههای اجتماعی
فرض کنید یک شبکهٔ اجتماعی کوچک شامل $5$ کاربر به نامهای $P_1$ تا $P_5$ داریم. ارتباط «دنبال کردن» در این شبکه به صورت زیر است: $P_1$ دنبالکنندهٔ $P_2$ و $P_3$ است. $P_2$ دنبالکنندهٔ $P_1$ و $P_4$ است. $P_3$ دنبالکنندهٔ $P_4$ و $P_5$ است. دیگر هیچ ارتباطی وجود ندارد.
حال همسایگی باز هر رأس را بررسی میکنیم: برای $P_1$ اعضای مجموعه $N(P_1)$ عبارتند از $\{P_2, P_3\}$. برای $P_2$ داریم $N(P_2) = \{P_1, P_4\}$. برای $P_3$ همسایگی باز برابر $\{P_4, P_5\}$ است. $P_4$ فقط دنبالکنندهٔ $P_2$ و $P_3$ است؛ پس $N(P_4) = \{P_2, P_3\}$. در نهایت $P_5$ فقط از $P_3$ دنبال میشود، بنابراین $N(P_5) = \{P_3\}$.
این مثال نشان میدهد که چگونه مفهوم همسایگی باز به ما کمک میکند تا تأثیر مستقیم هر کاربر بر کاربران دیگر (بدون احتساب خودش) را اندازه بگیریم. در الگوریتمهای پیشنهاددهندهٔ محتوا، معمولاً از همین مفهوم برای پیدا کردن سلایق مشترک استفاده میشود.
درجهٔ رأس و رابطهٔ آن با همسایگی باز
درجهٔ یک رأس4 در گراف ساده، برابر است با تعداد یالهایی که به آن رأس متصل هستند. از آنجایی که هر یال رأس مورد نظر را دقیقاً به یک رأس دیگر متصل میکند، درجهٔ رأس $v$ برابر است با تعداد اعضای همسایگی باز آن. به عبارت ریاضی:
برای مثال، در یک گراف چرخمانند با $6$ رأس که رأس مرکزی به همهٔ رأسهای دیگر متصل است، درجهٔ رأس مرکزی برابر $5$ و همسایگی باز آن شامل $5$ عضو است. در مقابل، رأسهای پیرامونی که فقط به رأس مرکزی و همسایهٔ کناری خود متصل هستند، درجهٔ $2$ و همسایگی باز $2$ عضوی دارند.
چالشهای مفهومی در درک همسایگی باز
چالش ۱: آیا همیشه همسایگی باز یک رأس با همسایگی باز رأس دیگر متفاوت است؟
پاسخ: نه لزوماً. دو رأس مختلف میتوانند همسایگی باز یکسانی داشته باشند. برای مثال، در یک گراف دووجهی (bipartite) کامل $K_{2,3}$، دو رأس از بخش کوچکتر (با $2$ عضو) هر دو به همهٔ $3$ رأس بخش دیگر متصل هستند، بنابراین همسایگی باز یکسانی دارند.
چالش ۲: آیا رأس مجزا (isolated vertex) همسایگی باز دارد؟
پاسخ: بله، اما همسایگی باز آن مجموعهٔ تهی یا empty set است. درجهٔ چنین رأسی $0$ است و $N(v) = \varnothing$. این حالت زمانی رخ میدهد که رأس هیچ یالی به رأس دیگر ندارد.
چالش ۳: در گراف جهتدار5، همسایگی باز چگونه تعریف میشود؟
پاسخ: در گراف جهتدار (که یالها جهت دارند)، دو نوع همسایگی باز داریم: همسایگی خروجی (رأسهایی که از $v$ به آنها یال میرود) و همسایگی ورودی (رأسهایی که از آنها به $v$ یال میرود). در گراف بدون جهت، این دو یکی هستند.
کاربرد عملی: الگوریتم جستجوی همسایگی
فرض کنید شما یک نقشه از اتاقهای یک موزه دارید که در آن هر اتاق یک رأس و راهروهای بین اتاقها یالهای گراف هستند. اگر بخواهید از یک اتاق مشخص، همهٔ اتاقهایی را که فقط یک راهرو با آن فاصله دارند پیدا کنید، دقیقاً دارید همسایگی باز آن رأس را محاسبه میکنید. این ایده پایهٔ بسیاری از الگوریتمهای مسیریابی مانند الگوریتم جستجوی اول سطح (BFS) است که در آن ابتدا همسایگان باز یک رأس بررسی میشوند، سپس همسایگان آن همسایگان و الی آخر.
در علم شیمی، وقتی ساختار مولکولی را به صورت گراف مدل میکنیم (اتمها رأس و پیوندها یال)، همسایگی باز یک اتم نشاندهندهٔ اتمهایی است که مستقیماً با آن پیوند دارند. این اطلاعات برای پیشبینی واکنشپذیری مولکول بسیار مهم است.
پاورقی
1 گراف (Graph): ساختاری ریاضی شامل مجموعهای از رأسها و یالها که روابط بین آنها را نشان میدهد.
2 رأس (Vertex): یک نقطه یا گره در گراف که میتواند به سایر رأسها متصل شود.
3 یال (Edge): ارتباط مستقیم بین دو رأس در گراف که به صورت خط یا منحنی نمایش داده میشود.
4 درجهٔ رأس (Degree of a Vertex): تعداد یالهای متصل به یک رأس در گراف بدون جهت و بدون حلقه.
5 گراف جهتدار (Directed Graph): گرافی که در آن هر یال دارای جهت بوده و از یک رأس به رأس دیگر اشاره میکند.
