مجموعهٔ احاطهگر گراف: معرفی، روشها و کاربردها
مفاهیم پایه، الگوریتم یافتن، مثالهای علمی و چالشهای موجود در نظریهٔ مجموعههای احاطهگر در گرافها
در این مقاله با مفهوم «مجموعهٔ احاطهگر» در گرافها آشنا میشوید. مجموعهٔ احاطهگر، زیرمجموعهای از رأسهاست که هر رأس گراف یا خودش در این مجموعه باشد یا با حداقل یک رأس از آن مجموعه مجاورت داشته باشد. کاربرد این مفهوم در مسائل بهینهسازی، شبکههای حسگر، پایش سیستمها و شناسایی مؤلفههای کلیدی در ساختارهای شبکهای دیده میشود. در این مقاله مثالهای متنوع، جدول مقایسه، چالشهای مفهومی و روشهای عددی ارائه شده است.
تعریف دقیق و اجزای تشکیلدهنده
گراف از دو مجموعه ساخته میشود: مجموعهٔ رأسها ($V$) و مجموعهٔ یالها ($E$). فرض کنید $G=(V,E)$ یک گراف ساده و بدون جهت باشد. یک زیرمجموعه مانند $D \subseteq V$ را مجموعهٔ احاطهگر1 گوییم هرگاه هر رأس $v \in V$ یا خودش عضو $D$ باشد یا با حداقل یک رأس از $D$ مجاور باشد. به عبارت دیگر، همهٔ رأسهای گراف توسط رأسهای $D$ «پوشش» داده میشوند. کوچکترین اندازهٔ ممکن برای چنین مجموعهای را عدد احاطهگر2 مینامیم و با $\gamma(G)$ نشان میدهیم.
مثال عملی فرض کنید شهری با $7$ محله (رأس) داریم که جادهها (یالها) ارتباط بین محلهها را نشان میدهند. میخواهیم ایستگاههای پلیس را در برخی محلهها مستقر کنیم به گونهای که هر محله یا خودش ایستگاه داشته باشد یا در مجاورت یک محلهٔ دارای ایستگاه باشد. یافتن کمترین تعداد ایستگاه مورد نیاز، همان یافتن عدد احاطهگر است.
انواع مجموعههای احاطهگر و ویژگیهای آنها
مجموعههای احاطهگر انواع گوناگونی دارند که در جدول زیر به مقایسهٔ چند نوع مهم پرداخته شده است:| نوع مجموعه | شرط تعریف | کاربرد معمول |
|---|---|---|
| مجموعهٔ احاطهگر مینیمال | با حذف هر عضو، احاطهگری از بین میرود | بهینهسازی محلی |
| مجموعهٔ احاطهگر مطلقاً مینیمال | هیچ زیرمجموعهٔ سرهای احاطهگر نیست | یافتن کوچکترین جواب |
| مجموعهٔ احاطهگر همبند | زیرگراف تحریکشده توسط $D$ همبند است | شبکههای ارتباطی |
برای گراف مسیر $P_n$ با $n$ رأس، عدد احاطهگر برابر است با $\lceil \frac{n}{3} \rceil$. برای مثال در مسیر $P_4$ با رأسهای $v_1-v_2-v_3-v_4$، مجموعهٔ $\{v_2, v_4\}$ یک مجموعهٔ احاطهگر با اندازهٔ $2$ است و عدد احاطهگر برابر $\lceil 4/3 \rceil = 2$ میشود.
روش گامبهگام یافتن مجموعهٔ احاطهگر در یک گراف کوچک
فرض کنید گرافی با $5$ رأس به صورت حلقهٔ $C_5$ داریم که رأسهای آن به ترتیب $a,b,c,d,e$ به صورت دایرهای به هم متصل شدهاند. مراحل یافتن یک مجموعهٔ احاطهگر کوچک:- گام 1: درجهٔ هر رأس را میشماریم (در حلقه $C_5$ همه درجه $2$ دارند).
- گام 2: یک رأس دلخواه مثل $a$ را به مجموعه اضافه میکنیم. حالا $a$ و همسایههایش ($b$ و $e$) پوشش داده شدند.
- گام 3: از بین رأسهای پوششنشده ($c$ و $d$) رأس $c$ را انتخاب میکنیم (چون با $d$ مجاور است). با افزودن $c$، $c$ و $d$ پوشش داده میشوند.
- گام 4: مجموعهٔ $\{a,c\}$ همهٔ رأسها را میپوشاند. بنابراین یک مجموعهٔ احاطهگر با اندازهٔ $2$ یافتیم.
$\gamma(C_5)=2$ در حالی که $|V|=5$ است. این نشان میدهد با کمتر از نصف رأسها هم میتوان کل گراف را احاطه کرد.
کاربرد عملی: شبکهٔ حسگرهای بیسیم
در یک مزرعهٔ هوشمند، $n$ گره حسگر داریم که هر حسگر بتواند با حسگرهای مجاور خود ارتباط برقرار کند (گراف ارتباطی). میخواهیم کمترین تعداد ایستگاههای دریافت داده را نصب کنیم به طوری که هر حسگر یا خودش ایستگاه باشد یا با یک ایستگاه هممجاور باشد. این دقیقاً همان مسئلهٔ یافتن مجموعهٔ احاطهگر است. با استفاده از الگوریتم حریصانه (هر بار انتخاب رأس با بیشترین تعداد همسایهٔ پوششنشده) میتوان جواب تقریبی و نزدیک به بهینه یافت. برای گرافهای خاص مانند درختها، الگوریتمهای دقیق با مرتبهٔ زمانی $O(n)$ وجود دارد.چالشهای مفهومی
پرسش 1: آیا مجموعهٔ احاطهگر یک گراف میتواند تهی ($D=\varnothing$) باشد؟
پاسخ: خیر، مگر آنکه گراف هیچ رأسای نداشته باشد ($|V|=0$). اگر حداقل یک رأس وجود داشته باشد، آن رأس برای احاطه شدن باید خودش در $D$ باشد یا با عضوی از $D$ مجاور باشد. مجموعهٔ تهی این شرط را برآورده نمیکند پس هر گراف غیرتهی عدد احاطهگر مثبتی دارد.
پاسخ: خیر، مگر آنکه گراف هیچ رأسای نداشته باشد ($|V|=0$). اگر حداقل یک رأس وجود داشته باشد، آن رأس برای احاطه شدن باید خودش در $D$ باشد یا با عضوی از $D$ مجاور باشد. مجموعهٔ تهی این شرط را برآورده نمیکند پس هر گراف غیرتهی عدد احاطهگر مثبتی دارد.
پرسش 2: آیا عدد احاطهگر همیشه از $\frac{|V|}{2}$ کوچکتر یا مساوی است؟
پاسخ: نه، برای مثال در گراف ستارهٔ $K_{1,n-1}$ با یک رأس مرکزی و $n-1$ برگ، عدد احاطهگر برابر $1$ است (فقط رأس مرکزی) که کمتر از نصف است. اما در گراف کامل $K_n$ هر رأس با بقیه مجاور است پس یک رأس کافی است. در گرافهایی مانند مسیر $P_n$، عدد احاطهگر تقریباً $n/3$ است که کمتر از نصف است. در حقیقت برای هر گراف بدون رأس تنها، نابرابری $\gamma(G) \le \frac{|V|}{2}$ همیشه برقرار نیست؟ بله برای گرافهایی با یال کم ممکن است به نصف نزدیک شود ولی مثال نقض برای بیشتر از نصف وجود دارد؟ در گراف دوبخشی کامل $K_{m,n}$ با $m\le n$، عدد احاطهگر برابر $m$ است که اگر $m > \frac{m+n}{2}$ نادر است چون $m \le n$ پس $m \le \frac{m+n}{2}$. در کل برای گرافهای ساده حد بالای $n/2$ همیشه برقرار نیست؟ یک مثال: گراف حاصل از اجتماع دو مؤلفهٔ $K_2$ (دو یال مجزا) با $4$ رأس، هر مؤلفه نیاز به یک رأس دارد پس $\gamma=2 = n/2$. اگر هر مؤلفه یک رأس تنها (بدون یال) داشته باشیم، آن رأس حتماً باید در مجموعه باشد پس برای $k$ رأس تنها، $\gamma = k = n$ که بزرگتر از $n/2$ است. اما گراف بدون یال مجاز نیست؟ در تعریف گراف ساده، رأس تنها مجاز است. بنابراین عدد احاطهگر میتواند تا $n$ هم برسد (مجموعهٔ همهٔ رأسها). در نتیجه نابرابری مطلق $\gamma(G) \le n/2$ نادرست است.
پاسخ: نه، برای مثال در گراف ستارهٔ $K_{1,n-1}$ با یک رأس مرکزی و $n-1$ برگ، عدد احاطهگر برابر $1$ است (فقط رأس مرکزی) که کمتر از نصف است. اما در گراف کامل $K_n$ هر رأس با بقیه مجاور است پس یک رأس کافی است. در گرافهایی مانند مسیر $P_n$، عدد احاطهگر تقریباً $n/3$ است که کمتر از نصف است. در حقیقت برای هر گراف بدون رأس تنها، نابرابری $\gamma(G) \le \frac{|V|}{2}$ همیشه برقرار نیست؟ بله برای گرافهایی با یال کم ممکن است به نصف نزدیک شود ولی مثال نقض برای بیشتر از نصف وجود دارد؟ در گراف دوبخشی کامل $K_{m,n}$ با $m\le n$، عدد احاطهگر برابر $m$ است که اگر $m > \frac{m+n}{2}$ نادر است چون $m \le n$ پس $m \le \frac{m+n}{2}$. در کل برای گرافهای ساده حد بالای $n/2$ همیشه برقرار نیست؟ یک مثال: گراف حاصل از اجتماع دو مؤلفهٔ $K_2$ (دو یال مجزا) با $4$ رأس، هر مؤلفه نیاز به یک رأس دارد پس $\gamma=2 = n/2$. اگر هر مؤلفه یک رأس تنها (بدون یال) داشته باشیم، آن رأس حتماً باید در مجموعه باشد پس برای $k$ رأس تنها، $\gamma = k = n$ که بزرگتر از $n/2$ است. اما گراف بدون یال مجاز نیست؟ در تعریف گراف ساده، رأس تنها مجاز است. بنابراین عدد احاطهگر میتواند تا $n$ هم برسد (مجموعهٔ همهٔ رأسها). در نتیجه نابرابری مطلق $\gamma(G) \le n/2$ نادرست است.
پرسش 3: آیا محاسبهٔ عدد احاطهگر برای هر گرافی سریع و آسان است؟
پاسخ: خیر، مسئلهٔ یافتن عدد احاطهگر برای گرافهای عمومی $\mathcal{NP}$-سخت است. یعنی الگوریتمی با زمان چندجملهای برای همهٔ گرافها شناخته نشده است. با این حال برای کلاسهای خاص مانند درختها، گرافهای مسیر، دور و گرافهای دوبخشی خاص، راهکارهای سریع وجود دارد.
پاسخ: خیر، مسئلهٔ یافتن عدد احاطهگر برای گرافهای عمومی $\mathcal{NP}$-سخت است. یعنی الگوریتمی با زمان چندجملهای برای همهٔ گرافها شناخته نشده است. با این حال برای کلاسهای خاص مانند درختها، گرافهای مسیر، دور و گرافهای دوبخشی خاص، راهکارهای سریع وجود دارد.
جمعبندی
مجموعهٔ احاطهگر یکی از مفاهیم پایهای در نظریهٔ گراف است که با انتخاب حداقل رأسهای تأثیرگذار، امکان پوشش کل رأسهای گراف را فراهم میکند. این مفهوم در مسائل بهینهسازی در شبکههای ارتباطی، سنسورها، شناسایی گرههای کلیدی و نظریهٔ کدگذاری کاربرد گسترده دارد. در این مقاله با انواع مجموعههای احاطهگر، روش گامبهگام یافتن آنها، مثالهای عددی و چالشهای محاسباتی آشنا شدید. درک این مفهوم پایهای برای ورود به مباحث پیشرفتهتر مانند احاطهگری در گرافهای وزندار، مجموعههای احاطهگر همبند و کاربردهای الگوریتمی ضروری است.
پاورقی
1 مجموعهٔ احاطهگر (Dominating Set): زیرمجموعهای از رأسهای گراف که هر رأس دیگر یا خود در آن مجموعه است یا با حداقل یک عضو از آن مجاور باشد.
2 عدد احاطهگر (Domination Number): کوچکترین اندازهٔ ممکن برای یک مجموعهٔ احاطهگر در گراف داده شده که با $\gamma(G)$ نمایش داده میشود.