مجموعهٔ احاطهگر مینیمال گراف: مفهوم، ویژگیها و کاربردها
تعریف پایه و پیشنیازهای گرافی
پیش از پرداختن به مجموعهٔ احاطهگر مینیمال، بهتر است چند مفهوم پایهای را مرور کنیم. گراف $G$ از دو جزء اصلی ساخته میشود: مجموعهٔ رأسها (رأسها) و مجموعهٔ یالها (پارها). دو رأس مجاور نامیده میشوند اگر بین آنها یک یال وجود داشته باشد. در زندگی روزمره میتوانید گراف را مانند نقشهٔ یک شبکهٔ دوستی تصور کنید: هر شخص یک رأس است و اگر دو نفر با هم دوست باشند، بینشان یک یال رسم میشود.
یک مجموعهٔ احاطهگر1 مانند $S \subseteq V$ در گراف $G = (V, E)$ دارای این ویژگی است که هر رأس در $V$ یا عضو $S$ است یا حداقل با یک رأس در $S$ مجاورت دارد. به عبارت دیگر، $S$ تمام گراف را میپوشاند. مجموعهٔ احاطهگر مینیمال2 مجموعهای است که خود احاطهگر بوده و هیچ زیرمجموعهٔ سرهای از آن احاطهگر نباشد. این یعنی اگر هر عضو را از آن حذف کنیم، مجموعه توانایی پوشش دادن تمام رأسها را از دست میدهد.
مقایسه مجموعه احاطهگر معمولی با مینیمال
برای درک بهتر تفاوت، جدول زیر ویژگیهای دو نوع مجموعه را مقایسه میکند:
| ویژگی | مجموعه احاطهگر معمولی | مجموعه احاطهگر مینیمال |
|---|---|---|
| شرط احاطهگری | برقرار است | برقرار است |
| شرط مینیمال بودن | الزامی نیست | الزامی است |
| حذف یک عضو | ممکن است همچنان احاطهگر بماند | احاطهگری از بین میرود |
| اندازه (تعداد اعضا) | میتواند بزرگ باشد | تا حد ممکن کوچک، ولی لزوماً مینیمم نیست |
یک مثال ساده: گرافی با سه رأس که به صورت زنجیرهای به هم وصل شدهاند (رأس الف – رأس ب – رأس ج). مجموعهٔ $\{الف, ج\}$ یک مجموعهٔ احاطهگر مینیمال است. اگر رأس الف را حذف کنیم، رأس ج به تنهایی نمیتواند رأس ب را بپوشاند (چون رأس ب با ج مجاور نیست). اگر رأس ج را حذف کنیم نیز به همین ترتیب احاطهگری از بین میرود. اما مجموعهٔ $\{الف, ب, ج\}$ هم احاطهگر است ولی مینیمال نیست چون با حذف مثلاً رأس ب، دو رأس الف و ج همچنان رأس ب را میپوشانند.
الگوریتم گامبهگام برای یافتن مجموعه احاطهگر مینیمال
برای پیدا کردن یک مجموعهٔ احاطهگر مینیمال در یک گراف کوچک، میتوانیم از روش سادهٔ زیر استفاده کنیم:
- یک مجموعهٔ احاطهگر دلخواه مانند $S$ انتخاب کنید (برای شروع میتوانید همهٔ رأسها را قرار دهید).
- هر رأس $v$ در $S$ را امتحان کنید: آیا $S \setminus \{v\}$ نیز احاطهگر است؟
- اگر بله، آن رأس را از $S$ حذف کنید و به مرحلهٔ $2$ برگردید.
- اگر خیر، آن رأس را نگه دارید و به سراغ رأس بعدی بروید.
- وقتی هیچ رأس دیگری قابل حذف نباشد، $S$ یک مجموعهٔ احاطهگر مینیمال است.
برای آشنایی بیشتر، یک مثال عملی در نظر بگیرید: گراف مسیر با $5$ رأس (نامگذاری شده با اعداد $1$ تا $5$ به صورت خطی). مجموعهٔ $\{2,4\}$ را در نظر بگیرید. رأس $1$ با رأس $2$ مجاور است، رأس $3$ با هر دو $2$ و $4$ مجاور است، رأس $5$ با رأس $4$ مجاور است. پس تک تک رأسها پوشانده شدهاند. آیا این مجموعه مینیمال است؟ اگر رأس $2$ را حذف کنیم، رأس $1$ بدون پوشش میماند (چون با $4$ مجاور نیست). اگر رأس $4$ را حذف کنیم، رأس $5$ بدون پوشش میماند. بنابراین $\{2,4\}$ یک مجموعهٔ احاطهگر مینیمال است.
کاربرد عملی: مسئلهٔ قرارگیری ایستگاههای پلیس
فرض کنید میخواهید در یک محله که نقشهٔ آن به صورت گراف است، ایستگاههای پلیس را به گونهای قرار دهید که هر خیابان (رأس) یا خودش ایستگاه داشته باشد یا در مجاورت (یک بلوک فاصله) با یک ایستگاه باشد. همچنین میخواهید هزینه را با کمترین تعداد ایستگاه بهینه کنید، اما به دلایل بودجهای نمیتوانید هیچ ایستگاه اضافی نگه دارید؛ یعنی اگر یک ایستگاه را بردارید، حتماً یک جای بدون پوشش باقی میماند. این دقیقاً همان مفهوم مجموعهٔ احاطهگر مینیمال است. برخلاف عدد احاطهگری4 (که کوچکترین مجموعهٔ احاطهگر است)، مجموعهٔ مینیمال الزاماً کوچکترین نیست، اما هیچ عضو اضافی ندارد.
مثالی دیگر: در شبکههای حسگر بیسیم، هر حسگر باید محدودهٔ مشخصی را پوشش دهد. مجموعهٔ حسگرهایی که فعال میمانند باید احاطهگر باشند و برای صرفهجویی در مصرف انرژی، هیچ حسگر اضافی (غیرضروری) نباید روشن بماند. این نیز نمونهای از کاربرد مجموعهٔ احاطهگر مینیمال است.
ویژگیهای مهم مجموعه احاطهگر مینیمال
چند ویژگی اساسی این مجموعهها را میتوان به صورت زیر دستهبندی کرد:
- یکتایی نیست: یک گراف میتواند چندین مجموعهٔ احاطهگر مینیمال مختلف با اندازههای متفاوت داشته باشد.
- شرط رأس تنها: در یک مجموعهٔ احاطهگر مینیمال، هر رأس عضو یا یک رأس تنها5 در بستهٔ همسایگی خودش است (یعنی رأس دیگری از مجموعه آن را نمیپوشاند) یا رئوس دیگری از مجموعه وجود دارند که آن را میپوشانند اما آن رأس برای پوشش رئوس دیگر ضروری است.
- ارتباط با مجموعهٔ مستقل: هر مجموعهٔ احاطهگر مینیمال مستقل6 (هیچ دو رأس مجاور هم نباشند) یک مجموعهٔ احاطهگر مینیمال است، اما عکس آن همیشه برقرار نیست.
آیا هر مجموعهٔ احاطهگر مینیمال، کوچکترین مجموعهٔ احاطهگر ممکن است؟
خیر. کوچکترین مجموعهٔ احاطهگر، «عدد احاطهگری» نام دارد و اندازهٔ آن با نماد $\gamma(G)$ نشان داده میشود. یک مجموعهٔ احاطهگر مینیمال میتواند بزرگتر از این مقدار باشد. به عبارت دیگر، «مینیمال» به معنای «مینیمم (کمترین)» نیست؛ بلکه به معنای «نمیتوان عضو حذف کرد» است.
چگونه میتوانیم در گرافهای بزرگ، مجموعهٔ احاطهگر مینیمال پیدا کنیم؟
برای گرافهای بزرگ، الگوریتم حریصانه (Greedy) کارآمد است: از یک مجموعهٔ احاطهگر بزرگ شروع کنید (مثلاً همهٔ رأسها) و تا زمانی که امکان حذف یک رأس بدون از دست رفتن خاصیت احاطهگری وجود دارد، آن را حذف کنید. این روش تضمین میکند خروجی نهایی مینیمال باشد.
تفاوت مجموعه احاطهگر مینیمال با مجموعه احاطهگر کمینه چیست؟
در متون علمی فارسی، «مینیمال» (minimal) و «کمینه» (minimum) دو مفهوم متفاوتند. مجموعهٔ «مینیمال» کوچکترین از نظر ترتیب جزئی (نمیتوان عضو کم کرد) و مجموعهٔ «کمینه» کوچکترین از نظر اندازه (کمترین تعداد عضو) است. مقالهٔ ما روی نوع اول (مینیمال) تمرکز دارد.
چالشهای مفهومی
۱) آیا مجموعهٔ خالی میتواند یک مجموعهٔ احاطهگر مینیمال باشد؟
خیر، مگر در گرافی با صفر رأس. در گراف با حداقل یک رأس، مجموعهٔ خالی احاطهگر نیست زیرا آن رأس بدون پوشش میماند. شرط اول (احاطهگری) برقرار نیست، بنابراین نمیتواند مینیمال باشد.
۲) در یک گراف کامل با $n$ رأس، مجموعهٔ احاطهگر مینیمال چه شکلی است؟
در گراف کامل $K_n$، هر رأس با همهٔ رئوس دیگر مجاور است. بنابراین هر مجموعهٔ تک عضوی احاطهگر است و به وضوح مینیمال هم هست (چون با حذف آن عضو، مجموعه خالی میشود و احاطهگری از بین میرود). مجموعههای با بیشتر از یک عضو نیز احاطهگر هستند اما مینیمال نیستند، زیرا میتوان یکی از اعضا را حذف کرد و همچنان مجموعه احاطهگر باقی بماند.
۳) آیا ممکن است در یک مسیر با $4$ رأس، دو مجموعهٔ احاطهگر مینیمال متفاوت با اندازهٔ یکسان وجود داشته باشد؟
بله. مسیر $P_4$ با رئوس $1-2-3-4$ را در نظر بگیرید. مجموعهٔ $\{2,4\}$ و مجموعهٔ $\{1,3\}$ هر دو احاطهگر مینیمال با اندازهٔ $2$ هستند. هر کدام را که بررسی کنید، حذف هر عضو باعث میشود یک رأس بدون پوشش بماند.
پاورقی
1 مجموعهٔ احاطهگر (Dominating Set): مجموعهای از رأسها در گراف که هر رأس دیگر یا خود در مجموعه است یا با یک عضو مجموعه مجاورت دارد.
2 مجموعهٔ احاطهگر مینیمال (Minimal Dominating Set): مجموعهٔ احاطهگری که با حذف هر یک از اعضایش، خاصیت احاطهگری از بین برود.
3 بستهٔ همسایگی (Closed Neighborhood): مجموعه شامل خود رأس و همهٔ رئوس مجاور به آن، که با $N[v]$ نشان داده میشود.
4 عدد احاطهگری (Domination Number): کوچکترین اندازهٔ ممکن برای یک مجموعهٔ احاطهگر در گراف، که با $\gamma(G)$ نمایش داده میشود.
5 رأس تنها (Private Neighbor): در یک مجموعهٔ احاطهگر، رأس $v$ برای رأس عضو $u$ یک رأس تنها است اگر در همسایگی بستهٔ $u$ باشد ولی در همسایگی بستهٔ هیچ عضو دیگری از مجموعه نباشد.
6 مجموعهٔ مستقل (Independent Set): مجموعهای از رأسها که هیچ دو رأس مجاوری با هم ندارند.
