احاطه کردن رأس: قرار داشتن رأس در مجموعهٔ احاطهگر یا مجاور بودن با یکی از اعضای آن
مفاهیم پایهای احاطهگری در گرافها: مجموعه احاطهگر، عدد احاطهگری و کاربردهای عملی در مدلسازی شبکه
این مقاله به مفهوم «احاطه کردن رأس» در نظریهٔ گراف میپردازد. شرط اصلی این است که هر رأس از گراف یا خود عضو مجموعهٔ احاطهگر باشد یا حداقل با یکی از اعضای آن مجاورت داشته باشد. با ارائهٔ تعاریف دقیق، مثالهای علمی و کاربردهای واقعی، درک این مبحث برای دانشآموزان دبیرستانی ساده و جذاب خواهد شد. همچنین عدد احاطهگری1، مجموعهٔ احاطهگر مینیمال2 و روشهای یافتن آنها در گرافهای مختلف بررسی میشود.
تعریف اصلی احاطهگری و شرط مجاورت
در نظریهٔ گراف3، فرض کنید $G = (V, E)$ یک گراف ساده و بدون جهت باشد که در آن $V$ مجموعهٔ رأسها و $E$ مجموعهٔ یالها است. یک مجموعه مانند $S \subseteq V$ را «مجموعهٔ احاطهگر» مینامیم، اگر و تنها اگر هر رأس $v \in V$ یا خود در $S$ قرار داشته باشد یا با حداقل یک رأس از $S$ مجاور باشد (یعنی یالی میان آنها وجود داشته باشد). شرط کلیدی این تعریف، پوشش کامل همهٔ رأسها از طریق «عضویت» یا «همسایگی» با اعضای مجموعهٔ احاطهگر است. به عبارت دیگر، مجموعهٔ $S$ باید به گونهای باشد که اجتماع $S$ و همسایههایش کل گراف را بپوشاند. برای روشنتر شدن مفهوم، یک مثال ساده در نظر بگیرید: یک گراف خطی با $4$ رأس متوالی به نامهای $v_1, v_2, v_3, v_4$ که هر رأس فقط به رأس قبلی و بعدی خود متصل است (به جز رأس اول و آخر). اگر مجموعهٔ $S = \{v_2, v_4\}$ را انتخاب کنیم، آیا همهٔ رأسها احاطه میشوند؟ رأس $v_2$ خودش در $S$ است. رأس $v_1$ با $v_2$ مجاور است. رأس $v_3$ با $v_2$ و $v_4$ هر دو مجاور است. رأس $v_4$ خودش عضو مجموعه است. بنابراین همهٔ رأسها احاطه شدهاند. پس $S$ یک مجموعهٔ احاطهگر است.انواع مجموعههای احاطهگر و عدد احاطهگری
در گرافها معمولاً مجموعههای احاطهگر متعددی وجود دارند. برخی از آنها بزرگ و برخی کوچک هستند. مهمترین مفهوم مرتبط، «عدد احاطهگری» است که با نماد $\gamma(G)$ نشان داده میشود و برابر است با اندازهٔ کوچکترین مجموعهٔ احاطهگر در گراف $G$. به چنین مجموعهای، «مجموعهٔ احاطهگر مینیمال2» از نظر تعداد اعضاء گفته میشود (نه لزوماً منحصربهفرد).
یک نکتهٔ مهم: مجموعهٔ احاطهگر «مینیمال» با «مجموعهٔ احاطهگر با کمترین اندازه» تفاوت دارد. مینیمال به مجموعهای گفته میشود که با حذف هر یک از اعضایش، خاصیت احاطهگری از بین برود. اما ممکن است چند مجموعهٔ مینیمال با اندازههای متفاوت وجود داشته باشند. کوچکترین آنها همان عدد احاطهگری را میدهد.
به عنوان مثال، در همان گراف خطی $4$ رأسی، مجموعهٔ $\{v_2, v_4\}$ با اندازهٔ $2$ یک مجموعهٔ احاطهگر است. اما میتوان مجموعهٔ $\{v_2\}$ را بررسی کرد: آیا تنها با $v_2$ همهٔ رأسها احاطه میشوند؟ رأس $v_4$ مجاور $v_2$ نیست (فاصله دارد) و خودش هم در مجموعه نیست. پس خیر. مجموعهٔ $\{v_1, v_3\}$ نیز احاطهگر است. آیا میتوان با $1$ رأس همه را پوشاند؟ خیر، زیرا هر رأس حداکثر $2$ همسایه دارد و کل گراف $4$ رأسی را یک رأس نمیتواند احاطه کند. بنابراین کوچکترین اندازه $2$ است و عدد احاطهگری $\gamma(G)=2$.
| مجموعهٔ پیشنهادی | آیا احاطهگر است؟ | اندازه | توضیح |
|---|---|---|---|
| $\{v_2\}$ | خیر | 1 | رأس $v_4$ احاطه نشده است. |
| $\{v_2, v_4\}$ | بله | 2 | همهٔ رأسها یا عضو یا مجاورند. |
| $\{v_1, v_3\}$ | بله | 2 | همچنین یک مجموعهٔ احاطهگر مینیمال. |
روش عملی یافتن مجموعهٔ احاطهگر در گرافهای ساده
برای پیدا کردن یک مجموعهٔ احاطهگر (و به ویژه کوچکترین آن) در گرافهای کوچک، میتوان از روش «حدس و بررسی سیستماتیک» استفاده کرد. گامهای پیشنهادی عبارتند از: ۱. ابتدا تمام رأسهایی که درجه4 بالایی دارند (یعنی به تعداد زیادی رأس دیگر متصل هستند) را علامت بزنید. این رأسها میتوانند همسایههای زیادی را پوشش دهند. ۲. یک مجموعهٔ اولیه شامل پر درجهترین رأس تشکیل دهید. ۳. رأسهایی را که هنوز احاطه نشدهاند (نه خودشان در مجموعه هستند و نه همسایهٔ هیچ عضوی از مجموعه) پیدا کنید. ۴. از میان رأسهای احاطهنشده، رأسهایی را انتخاب کنید که بیشترین رأس احاطهنشدهٔ دیگر را پوشش میدهند و به مجموعه اضافه کنید. ۵. این فرآیند را تا زمانی ادامه دهید که همهٔ رأسها احاطه شوند. مثال عینی فرض کنید گراف یک دوست در شبکهٔ اجتماعی مدرسه داریم: رأسها دانشآموزان هستند و یال نشاندهندهٔ دوستی است. میخواهیم گروهی از دانشآموزان (مجموعهٔ احاطهگر) را انتخاب کنیم به طوری که هر دانشآموز یا خودش در گروه باشد یا با یکی از اعضای گروه دوست باشد. این مسئله مشابه انتخاب «سرگروههای اطلاعرسانی» است تا همهٔ افراد خبر را دریافت کنند (اگر هر عضو گروه خبر را به دوستانش بگوید). کوچکترین چنین گروهی، عدد احاطهگری شبکهٔ دوستی را نشان میدهد.چالشهای مفهومی در احاطهسازی رأسها
۱. آیا هر رأس میتواند همزمان هم عضو مجموعهٔ احاطهگر باشد و هم مجاور با عضو دیگر؟
بله، این اشکالی ندارد. شرط احاطهگری فقط میگوید «یا خود عضو است یا مجاور با یک عضو». اگر رأس هم عضو باشد و هم مجاور باشد، همچنان شرط برقرار است. هیچ منعی برای این حالت وجود ندارد.
بله، این اشکالی ندارد. شرط احاطهگری فقط میگوید «یا خود عضو است یا مجاور با یک عضو». اگر رأس هم عضو باشد و هم مجاور باشد، همچنان شرط برقرار است. هیچ منعی برای این حالت وجود ندارد.
۲. آیا مجموعهٔ همهٔ رأسها همیشه یک مجموعهٔ احاطهگر است؟
قطعاً بله. اگر $S = V$ (همهٔ رأسها را برداریم)، آنگاه هر رأس خودش عضو $S$ است، پس شرط احاطهگری به راحتی برقرار است. اما این مجموعه معمولاً از نظر اندازه بهینه نیست و عدد احاطهگری گراف معمولاً بسیار کوچکتر از تعداد کل رأسها است.
قطعاً بله. اگر $S = V$ (همهٔ رأسها را برداریم)، آنگاه هر رأس خودش عضو $S$ است، پس شرط احاطهگری به راحتی برقرار است. اما این مجموعه معمولاً از نظر اندازه بهینه نیست و عدد احاطهگری گراف معمولاً بسیار کوچکتر از تعداد کل رأسها است.
۳. آیا در یک گراف بدون یال (تهی) میتوان مجموعهٔ احاطهگر غیر از همهٔ رأسها داشت؟
در گراف تهی هیچ یالی وجود ندارد، بنابراین هیچ رأسی با رأسی دیگر مجاور نیست. برای احاطه کردن یک رأس، تنها راه این است که خود رأس در مجموعه باشد. پس تنها مجموعهٔ احاطهگر، مجموعهٔ همهٔ رأسها است. در نتیجه عدد احاطهگری برابر با تعداد رأسها خواهد بود.
در گراف تهی هیچ یالی وجود ندارد، بنابراین هیچ رأسی با رأسی دیگر مجاور نیست. برای احاطه کردن یک رأس، تنها راه این است که خود رأس در مجموعه باشد. پس تنها مجموعهٔ احاطهگر، مجموعهٔ همهٔ رأسها است. در نتیجه عدد احاطهگری برابر با تعداد رأسها خواهد بود.
جمعبندی
مفهوم احاطه کردن رأس در نظریهٔ گراف، ابزاری قدرتمند برای تحلیل پوشش در شبکههاست. شرط اصلی «عضویت یا مجاورت» با مجموعهٔ احاطهگر، تعریفی ساده اما بنیادین ارائه میدهد. عدد احاطهگری ($\gamma(G)$) کوچکترین اندازهٔ چنین مجموعههایی است. شناخت روشهای یافتن مجموعههای احاطهگر مینیمال، به درک بهتر مسائل بهینهسازی در شبکههای ارتباطی، سنسورها و توزیع اطلاعات کمک میکند. در این مقاله با مثالهای متنوع و جدول مقایسه، نشان دادیم که چگونه میتوان یک مجموعهٔ احاطهگر را تشخیص داد و چرا برخی مجموعهها علیرغم کوچک بودن، احاطهگر نیستند.
پاورقی
1 عدد احاطهگری (Domination Number): کوچکترین اندازهٔ یک مجموعهٔ احاطهگر در گراف که با $\gamma(G)$ نمایش داده میشود.
2 مجموعهٔ احاطهگر مینیمال (Minimal Dominating Set): مجموعهای احاطهگر که با حذف هر یک از اعضایش، خاصیت احاطهگری از بین برود.
3 نظریهٔ گراف (Graph Theory): شاخهای از ریاضیات که به مطالعهٔ گرافها به عنوان ساختارهایی متشکل از رأس و یال میپردازد.
4 درجهٔ رأس (Degree of a Vertex): تعداد یالهایی که به یک رأس متصل هستند. در گراف ساده، برابر تعداد همسایههای آن رأس است.
