احاطهگری در گراف: پوشش دادن رأسها توسط یک مجموعه از رأسها
1. گراف چیست و چرا به احاطهگری نیاز داریم؟
گراف2 یک مدل ریاضی است که از رأسها (نقاط) و یالها (خطهای اتصال) تشکیل شده است. فرض کنید در یک شهر، چندین دوربین مداربسته میخواهید نصب کنید. هر دوربین فقط تقاطع خود (رأس) و تقاطعهای همسایه (مجاور) را پوشش میدهد. میخواهیم کمترین تعداد دوربین را نصب کنیم تا تمام تقاطعها پوشش داده شوند. این دقیقاً مسئله «مجموعه احاطهگر» است.
مثال ساده: یک گراف خطی با 5 رأس متوالی در نظر بگیرید. رأس شماره 2 و 4 را انتخاب کنید. رأس 1 با 2 و 3 با 2 یا 4 مجاور است. رأس 5 نیز با 4 مجاور است. همه رأسها پوشش داده شدند.
2. تعریف رسمی مجموعه احاطهگر و عدد احاطهگری
فرض کنید $G = (V, E)$ یک گراف ساده باشد، که $V$ مجموعه رأسها و $E$ مجموعه یالها است. مجموعه $S \subseteq V$ را یک مجموعه احاطهگر مینامیم اگر هر رأس در $V$ یا در $S$ باشد یا با حداقل یک رأس از $S$ مجاور باشد. عدد احاطهگری که با $\gamma(G)$ نشان داده میشود، اندازه کوچکترین مجموعه احاطهگر در گراف $G$ است.
| نوع گراف | تعداد رأسها ($n$) | عدد احاطهگری $\gamma(G)$ | توضیح |
|---|---|---|---|
| مسیر $P_n$ | 5 | 2 | انتخاب رأسهای دوم و چهارم |
| چرخه $C_n$ | 6 | 2 | دو رأس مقابل هم |
| ستاره $K_{1,3}$ | 4 | 1 | رأس مرکزی همه را میپوشاند |
3. مثال عینی: پوشش خبری در شبکه اجتماعی
فرض کنید یک شبکه اجتماعی با 7 کاربر داریم. یالها نشاندهنده رابطه دوستی هستند. میخواهیم گروهی از کاربران را به عنوان «تولیدکننده محتوا» انتخاب کنیم تا هر کاربر یا خودش تولیدکننده باشد یا با یک تولیدکننده دوست باشد. این دقیقاً همان مجموعه احاطهگر است. اگر گراف به صورت حلقه $C_7$ باشد، عدد احاطهگری برابر $\lceil 7/3 \rceil = 3$ است. یعنی با انتخاب سه نفر با فاصله مساوی، کل شبکه پوشش داده میشود.
در یک گراف مکعبی $Q_3$ (که 8 رأس دارد)، عدد احاطهگری برابر $2$ است. یعنی فقط دو رأس به خوبی انتخاب شده میتوانند تمام 8 رأس را بپوشانند. این مسئله در بهینهسازی پخش داده در شبکههای کامپیوتری کاربرد مستقیم دارد.
4. کاربرد عملی: مکانیابی ایستگاههای آتشنشانی
یک شهر را به صورت گراف مدل کنید که هر رأس یک محله و یالها نشاندهنده جادههای مستقیم بین محلهها هستند. ایستگاه آتشنشانی در یک محله میتواند به محله خود و همه محلههای مجاور (در فاصله یک یال) خدمات دهد. هدف: کمترین تعداد ایستگاه به طوری که هر محله پوشش داشته باشد. این مسئله معادل یافتن عدد احاطهگری گراف شهر است. الگوریتمهای حریصانه (با انتخاب رأس با بیشترین درجه پوششدهی) تقریب خوبی ارائه میدهند، هرچند یافتن دقیق مجموعه احاطهگر حداقلی یک مسئله انپی-سخت (NP-hard) است.
5. الگوریتم ساده برای یافتن مجموعه احاطهگر
یک روش ساده (اما کند) این است: همه زیرمجموعههای رأسها را از کوچک به بزرگ بررسی کنید و چک کنید که آیا هر رأس یا در زیرمجموعه است یا همسایه دارد. نخستین زیرمجموعهای که شرط را برآورده کند، مجموعه احاطهگر حداقلی است. برای گراف با $n$ رأس، $2^n$ زیرمجموعه وجود دارد، بنابراین فقط برای گرافهای کوچک (مثلاً $n \le 20$) قابل اجراست.
6. چالشهای مفهومی
پاسخ: خیر. در گراف تطابق کامل (شامل جفتهای مجزا) که هر یال دو رأس را به هم متصل کرده و هیچ یال دیگری وجود ندارد، هر مجموعه احاطهگر باید حداقل از هر یال یک رأس را شامل شود. بنابراین عدد احاطهگری برابر $n/2$ است.
پاسخ: نه لزوماً. اگر رأس حذفشده در همه مجموعههای احاطهگر حداقلی حضور داشته باشد، حذف آن ممکن است عدد احاطهگری را یک واحد کاهش دهد یا حتی ثابت نگه دارد. در گرافهای خاص، حذف یک رأس میتواند عدد احاطهگری را افزایش دهد زیرا ساختار مجاورت تغییر میکند.
پاسخ: بله. در هر گراف بدون رأس تنها، عدد استقلال (بزرگترین مجموعه رأسهای غیرمجاور) همواره از عدد احاطهگری بزرگتر یا مساوی است. همچنین یک نامساوی کلاسیک: $\gamma(G) \le \alpha(G)$ که در آن $\alpha(G)$ عدد استقلال است. برای گرافهای دوبخشی، رابطه دقیقتری برقرار است.
7. جمعبندی
پاورقی
1 عدد احاطهگری (Domination Number): کوچکترین اندازه یک مجموعه احاطهگر در گراف که با $\gamma(G)$ نمایش داده میشود.
2 گراف (Graph): ساختاری متشکل از رأسها (vertices) و یالها (edges) که روابط بین اشیاء را مدل میکند.
3 عدد استقلال (Independence Number): بزرگترین اندازه مجموعهای از رأسها که هیچ دو رأس آن مجاور نباشند.