احاطه بسته یک رأس: خود رأس همراه با همهٔ همسایههای آن
تعریف اصلی و نمایش گرافیکی
در نظریهٔ گراف3، یک گراف از مجموعهای از رأسها (یا گرهها) و یالها (پیوندها) تشکیل میشود. برای هر رأس دلخواه مانند $v$، همسایههای آن رأسهایی هستند که با $v$ با یک یال متصل شدهاند. اصطلاح «احاطه بسته» به مجموعهای گفته میشود که شامل خودِ رأس و همهٔ همسایههای آن باشد. نماد آن به صورت زیر است:
که در آن $N(v)$ مجموعهٔ همهٔ همسایههای $v$ است.
مثال ساده: فرض کنید در یک شبکهٔ دوستانه، رأس «علی» با «بهرام» و «پریسا» دوست است. اگر «علی» را در نظر بگیریم، مجموعهٔ احاطه بستهٔ «علی» شامل خودِ علی، بهرام و پریسا خواهد بود. این مجموعه در مسائل یافتن گروههای تأثیرگذار یا کنترل یک شبکه کاربرد دارد.
انواع گراف و رفتار مجموعه بستهٔ همسایگی
رفتار مجموعهٔ احاطه بسته به نوع گراف وابسته است. در جدول زیر ویژگیهای این مجموعه در چند گراف مشهور مقایسه شده است:
| نوع گراف | ویژگی احاطه بسته | مثال عددی |
|---|---|---|
| گراف کامل $K_n$ | هر رأس با همهٔ رأسهای دیگر همسایه است | $|N[v]| = n$ (کل رأسها) |
| گراف مسیر $P_n$ | برای رأس انتهایی $|N[v]| = 2$، برای رأس میانی $|N[v]| = 3$ | برای $P_5$، اندازه مجموعه بین $2$ تا $3$ |
| گراف ستاره $K_{1,3}$ | مرکز: خودش + همهٔ برگها (۴ رأس) - برگ: خودش + مرکز (۲ رأس) | $|N[\text{center}]|=4 , |N[\text{leaf}]|=2$ |
کاربرد عملی: مسئلهٔ آتشنشانی در یک محله
فرض کنید یک محله با $7$ خانه داریم که هر خانه یک رأس و راههای بین آنها یالها هستند. میخواهیم ایستگاههای آتشنشانی را طوری قرار دهیم که هر خانه یا خودش ایستگاه داشته باشد یا حداقل با یک خانهٔ دارای ایستگاه مجاور باشد. این همان مفهوم مجموعهٔ احاطهگر1 است. احاطه بسته یک رأس به ما نشان میدهد که با انتخاب یک رأس به عنوان ایستگاه، کدام خانهها پوشش داده میشوند. به عنوان مثال، اگر رأس $x$ را انتخاب کنیم، مجموعهٔ $N[x]$ خانههایی هستند که در امان میمانند. هدف یافتن کوچکترین تعداد رأسها است که اجتماع احاطه بستهٔ آنها کل گراف را بپوشاند.
یک مثال گامبهگام: گراف دوچرخهای با $6$ رأس (یک ششضلعی) در نظر بگیرید. برای رأس شماره $1$ با همسایههای $6$ و $2$، مجموعهٔ احاطه بسته $N[1]=\{1,6,2\}$ خواهد بود. انتخاب رأسهای $1$ و $4$ کل شش رأس را پوشش میدهد زیرا $N[1] \cup N[4] = \{1,2,6\} \cup \{4,5,3\} = V$.
روابط ریاضی و قضیه کران بالا
برای هر گراف با $n$ رأس و بیشینهٔ درجهٔ $\Delta$ (بیشترین تعداد همسایه برای یک رأس)، اندازهٔ مجموعهٔ احاطه بسته همواره بین $1$ و $\Delta+1$ است. یک قضیهٔ مهم در این زمینه:
و همچنین برای گرافهای بدون رأس تنها4، همیشه $|N[v]| \ge 2$.
اگر گراف منتظم5 از درجه $k$ باشد (همهٔ رأسها دقیقاً $k$ همسایه دارند)، آنگاه اندازهٔ احاطه بسته برای همهٔ رأسها یکسان و برابر $k+1$ میشود. مثال: در یک مکعب (گراف $3$-منتظم با $8$ رأس)، هر رأس دقیقاً $3$ همسایه دارد، پس $|N[v]| = 4$.
چالشهای مفهومی
پاسخ: بله، در گرافهایی که دو رأس همسایه بوده و بقیهٔ همسایههای آنها نیز یکسان باشند، چنین وضعیتی رخ میدهد. برای مثال در یک گراف مثلثی ($K_3$)، برای هر رأس داریم $N[v] = V$، بنابراین همهٔ مجموعهها برابر کل گراف هستند.
پاسخ: بله. در نظریهٔ استاندارد گراف ساده، حلقه مجاز نیست. اما اگر گراف دارای حلقه باشد، آن رأس خودش را نیز به عنوان همسایه خواهد داشت. در این صورت $N(v)$ شامل خود رأس میشود و $N[v]$ عملاً دوبار خودش را خواهد داشت که در مجموعهها تکراری محسوب نمیشود، اما اندازه تغییر نمیکند.
پاسخ: یکی از روشها، مرتبسازی رأسها بر اساس اندازهٔ $|N[v]|$ نزولی است. رأسهایی با مجموعهٔ بستهٔ بزرگتر، قدرت پوشش بیشتری دارند و در الگوریتمهای تقریبی برای مسئلهٔ مجموعهٔ احاطهگر ابتدا انتخاب میشوند. این ایده در مسیریابی شبکه و انتخاب گرههای کلیدی کاربرد دارد.
