همسایگی بستهٔ رأس در گراف: همسایگی باز به همراه خود رأس
۱. آشنایی با گراف و تعریف رأس و یال
گراف1 یک ساختار ریاضی است که از مجموعهای از رأسها (نقاط) و یالها (خطهای رابط) تشکیل میشود. اگر دو رأس توسط یک یال به هم وصل شده باشند، میگوییم آن دو رأس همسایه هستند. برای مثال، در یک نقشه از شهرها، هر شهر یک رأس و جاده بین دو شهر یک یال است.
فرض کنید گراف سادهای داریم با رأسهای $A, B, C, D$ که در آن $A$ به $B$ و $C$ متصل است، اما به $D$ متصل نیست. در این صورت همسایههای $A$ عبارتند از $B$ و $C$.
۲. تعریف همسایگی باز و همسایگی بسته
همسایگی باز یک رأس مانند $v$، که آن را با $N(v)$ نشان میدهند، مجموعهٔ تمام رأسهایی است که با $v$ مجاور هستند (یال مستقیم دارند) به جز خودِ$v$. اما همسایگی بسته که با نماد $N[v]$ نشان داده میشود، برابر است با اجتماع همسایگی باز و خود رأس: $N[v] = N(v) \cup \{v\}$.
به عبارت ساده، اگر از یک رأس بپرسیم «همسایههای تو چه کسانی هستند؟» در همسایگی باز فقط دیگران را معرفی میکند، ولی در همسایگی بسته خودش را هم به لیست اضافه میکند.
۳. تفاوت کلیدی همسایگی باز و بسته با مثال جدولی
برای روشن شدن تفاوت، گراف زیر را تصور کنید: رأسهای $X, Y, Z$ به صورت مثلثی به هم متصل هستند (هر جفت با یک یال). همسایگی باز و بسته برای هر رأس را در جدول مقایسه کردهایم.
| رأس | همسایگی باز $N(v)$ | همسایگی بسته $N[v]$ |
|---|---|---|
| $X$ | $\{Y, Z\}$ | $\{X, Y, Z\}$ |
| $Y$ | $\{X, Z\}$ | $\{Y, X, Z\}$ |
| $Z$ | $\{X, Y\}$ | $\{Z, X, Y\}$ |
همانطور که میبینید، همسایگی بسته همیشه یک عضو بیشتر از همسایگی باز دارد (همان خود رأس). به همین دلیل به آن «بسته» میگویند چون خودش را هم در بر میگیرد.
۴. کاربرد عملی همسایگی بسته در تحلیل شبکه و دوستیابی
تصور کنید در یک کلاس درس، گرافی رسم شده که در آن هر دانشآموز یک رأس است و اگر دو نفر با هم دوست باشند، یالی بینشان وجود دارد. اگر بخواهیم گروههای مطالعاتی تشکیل دهیم که هر عضو همراه با همهٔ دوستانش در یک گروه باشد، باید از مفهوم همسایگی بسته استفاده کنیم.
برای مثال، اگر «سارا» را در نظر بگیریم، همسایگی بستهٔ سارا شامل خود سارا و همهٔ دوستان مستقیم او میشود. این مجموعه میتواند یک گروه مطالعاتی ایدهآل باشد چون سارا میتواند با همهٔ اعضای گروه ارتباط مستقیم داشته باشد. شبکههای اجتماعی مانند تلگرام یا واتساپ هنگام پیشنهاد گروههای جدید، گاهی از همین مفهوم استفاده میکنند (پیشنهاد دوستان دوستان، اما با احتساب خود فرد).
۵. چالشهای مفهومی در همسایگی بسته
پرسش ۱: آیا همسایگی بسته برای یک رأس تنها (بدون هیچ یالی) چگونه تعریف میشود؟
پاسخ: بله. اگر رأس $v$ هیچ همسایهای نداشته باشد (رأس تنها یا منزوی)، آنگاه $N(v) = \emptyset$ (مجموعهٔ خالی) است. اما همسایگی بسته برابر $N[v] = \{v\}$ خواهد بود. پس حتی یک رأس تنها در همسایگی بستهٔ خودش حضور دارد.
پرسش ۲: آیا ممکن است همسایگی بستهٔ دو رأس مختلف با هم برابر باشد؟
پاسخ: بله، امکان دارد. در یک گراف کامل (که هر رأس به همهٔ رأسهای دیگر متصل است)، برای هر رأس $v$، همسایگی بسته برابر با مجموعهٔ تمام رأسهای گراف است. بنابراین برای هر دو رأس $v$ و $u$ خواهیم داشت $N[v] = N[u]$. به این حالت «همسایگی بسته یکسان» میگویند.
پرسش ۳: چه رابطهای بین همسایگی بسته و مفهوم «زیرگراف القایی» وجود دارد؟
پاسخ: اگر مجموعهٔ رأسهای همسایگی بستهٔ رأس $v$ را در نظر بگیریم، زیرگرافی که روی این مجموعه از رأسها توسط گراف اصلی القا میشود، شامل خود $v$ و تمام یالهای بین همسایههایش (به جز یالهایی که به خارج از مجموعه وصل میشوند) خواهد بود. این زیرگراف، همسایگی بستهٔ القایی نام دارد و در مسائل رنگآمیزی گراف کاربرد دارد.
۶. ویژگیهای جالب همسایگی بسته به صورت فهرست وار
در زیر مهمترین ویژگیهای همسایگی بسته را مرور میکنیم:
- هر رأس همواره عضو همسایگی بستهٔ خودش است ($v \in N[v]$).
- اندازهٔ همسایگی بسته برابر است با $\deg(v) + 1$ در گراف ساده (بدون حلقه و یال چندگانه).
- اگر $u$ و $v$ مجاور باشند، آنگاه $u \in N[v]$ و $v \in N[u]$.
- همسایگی بسته برای گرافهای بدون جهت متقارن است: $u \in N[v] \iff v \in N[u]$.
۷. جدول مقایسهٔ کاربردها در موقعیتهای مختلف
| موقعیت / کاربرد | همسایگی باز مناسب است؟ | همسایگی بسته مناسب است؟ |
|---|---|---|
| شناخت دوستان یک فرد (به جز خودش) | بله | خیر (خود فرد را هم شامل میشود) |
| تشکیل تیم شامل خود فرد و همکاران مستقیم | خیر (فرد را شامل نمیشود) | بله |
| محاسبهٔ درجهٔ رأس (تعداد همسایهها) | بله | خیر (درجه به اضافه یک میدهد) |
۸. تمرین گام به گام برای تثبیت یادگیری
گراف زیر را در نظر بگیرید: رأسهای $P, Q, R, S$ به طوری که $P$ به $Q$ و $R$ وصل است، $Q$ به $P$ و $S$ وصل است، $R$ فقط به $P$ وصل است، و $S$ فقط به $Q$ وصل است.
- همسایگی باز هر رأس را بنویسید.
- همسایگی بستهٔ هر رأس را بنویسید.
- رأسی را پیدا کنید که همسایگی بستهٔ آن بیشترین اندازه را دارد.
پاسخ:$N(P) = \{Q,R\}, N(Q) = \{P,S\}, N(R) = \{P\}, N(S) = \{Q\}$. همسایگیهای بسته: $N[P] = \{P,Q,R\}, N[Q] = \{Q,P,S\}, N[R] = \{R,P\}, N[S] = \{S,Q\}$. بیشترین اندازه مربوط به $P$ و $Q$ با اندازهٔ $3$ است.
پاورقی
1 گراف (Graph): ساختاری ریاضی متشکل از مجموعهٔ رأسها (نقاط) و مجموعهٔ یالها (ارتباطات) که روابط زوجی بین رأسها را نشان میدهد.
2 همسایگی باز (Open Neighborhood): مجموعهٔ تمام رأسهایی که با یک رأس مشخص مجاور هستند، بدون احتساب خود آن رأس.
3 همسایگی بسته (Closed Neighborhood): اجتماع همسایگی باز با خود رأس که شامل رأس مورد نظر و همهٔ همسایههایش میشود.
4 درجهٔ رأس (Degree of a Vertex): تعداد یالهایی که به یک رأس متصل هستند؛ در گراف ساده برابر تعداد همسایههای آن رأس است.
