مسئلهٔ نصب خودپرداز: نمونهای از کاربرد مجموعهٔ احاطهگر در شهر
انتخاب حداقل مکانها برای پوشش حداکثری خدمات: آشنایی با مسئله مجموعه احاطهگر (Dominating Set) در گراف شهر
در این مقاله با مسئلهٔ نصب خودپرداز در یک شهر آشنا میشوید. میآموزید که چگونه با استفاده از «مجموعه احاطهگر» در نظریهٔ گراف1، کمترین تعداد دستگاه خودپرداز را طوری نصب کنیم که هر تقاطع یا بلوک شهری یا در محل نصب دستگاه قرار گیرد یا در همسایگیِ یک دستگاه باشد. این مسئله کاربرد گستردهای در مکانیابی ایستگاههای آتشنشانی، دوربینهای مداربسته و حسگرهای بیسیم دارد.
نمایش شهر به عنوان یک گراف
برای حل مسئله، ابتدا نقشهٔ شهر را به یک گراف تبدیل میکنیم. هر تقاطع یا میدان مهم را یک رأس و هر خیابان مستقیم بین دو تقاطع را یک یال در نظر میگیریم. در این مدلسازی، دو رأس مجاور (همسایه) هستند اگر یک یال مستقیم آنها را به هم وصل کند.به عنوان مثال، فرض کنید یک شهر کوچک دارای 5 تقاطع A، B، C، D و E است که خیابانها به صورت زیر آنها را متصل کردهاند: A به B، A به C، B به C، B به D، C به E و D به E. این شهر با گراف زیر نمایش داده میشود.
| نام تقاطع | همسایههای مستقیم | ||||||||
|---|---|---|---|---|---|---|---|---|---|
| A | B , C | B | A , C , D | C | A , B , E | D | B , E | E | C , D |
تعریف مجموعهٔ احاطهگر (Dominating Set)
در نظریهٔ گراف، به مجموعهای از رأسها مجموعه احاطهگر میگوییم که هر رأس گراف یا خود عضو این مجموعه باشد یا حداقل یک همسایه در این مجموعه داشته باشد. به عبارت دیگر، مجموعه احاطهگر تمام رأسهای گراف را «پوشش» میدهد.فرمول ریاضی
اگر $G = (V, E)$ یک گراف با مجموعه رأسهای $V$ و یالهای $E$ باشد، مجموعه $S \subseteq V$ یک مجموعه احاطهگر است اگر برای هر رأس $v \in V$ داشته باشیم: $v \in S$ یا $\exists u \in S \quad (v,u) \in E$.
در مسئلهٔ خودپردازها، هر خودپرداز در یک تقاطع نصب میشود و به ساکنان همان تقاطع و تقاطعهای همسایه (مجاور) سرویس میدهد. هدف ما یافتن مجموعه احاطهگر با کمترین اندازه (حداقل تعداد خودپرداز) است که به آن «عدد احاطهگری» میگویند.
اگر $G = (V, E)$ یک گراف با مجموعه رأسهای $V$ و یالهای $E$ باشد، مجموعه $S \subseteq V$ یک مجموعه احاطهگر است اگر برای هر رأس $v \in V$ داشته باشیم: $v \in S$ یا $\exists u \in S \quad (v,u) \in E$.
مثال گامبهگام حداقل خودپرداز در شهر نمونه
برای گراف شهر 5 رأسای بالا (A تا E)، میخواهیم کمترین تعداد تقاطعهایی را بیابیم که اگر در آنها خودپرداز نصب کنیم، هر تقاطع یا خودش خودپرداز داشته باشد یا در کنار یک خودپرداز قرار گیرد.- ابتدا سعی میکنیم با 1 خودپرداز کار کنیم. آیا رأس خاصی وجود دارد که همهٔ رأسها خود آن رأس یا همسایه آن باشند؟ با نگاه به جدول همسایگی، رأس B به A، C، D متصل است و خود B نیز شمرده میشود. اما رأس E همسایه B نیست (E فقط به C و D متصل است). پس B نمیتواند E را پوشش دهد. رأس C نیز E و A و B را پوشش میدهد ولی D را پوشش نمیدهد (D همسایه C نیست). بنابراین با 1 خودپرداز نمیتوان کل گراف را پوشاند.
- اکنون با 2 خودپرداز امتحان میکنیم. مجموعه {B, E} را در نظر بگیرید:
- B: خودش و همسایگانش (A, C, D) پوشیده شدند. - E: خودش و همسایگانش (C, D) پوشیده شدند. تمام رأسها (A, B, C, D, E) پوشیده شدهاند. بنابراین {B, E} یک مجموعه احاطهگر است. - آیا مجموعهای با 2 عضو دیگر نیز جواب میدهد؟ بله، مجموعه {C, D} نیز تمام رأسها را میپوشاند. اما هیچ مجموعهٔ 1 عضوی جوابگو نبود، بنابراین عدد احاطهگری این گراف برابر 2 است.
مثال عینی: فرض کنید شهرداری بودجهٔ کافی فقط برای خرید 2 دستگاه خودپرداز دارد. با تحلیل گراف شهر (نمونهٔ بالا)، مدیر شهری میتواند تقاطعهای B و E را انتخاب کند. در این حالت، حتی ساکنان تقاطع A که خودپرداز ندارند، میتوانند از خودپرداز B (که در همسایگی است) استفاده کنند. این شیوه، هزینه را بهینه میکند و خدمات را به همه میرساند.
مقایسه انواع مجموعههای احاطهگر
در مسئله مکانیابی، گاهی اهداف متفاوتی داریم. جدول زیر سه نوع مجموعه احاطهگر معروف را مقایسه میکند:| نوع مجموعه | شرط اضافی | کاربرد در شهر | ||||||
|---|---|---|---|---|---|---|---|---|
| مجموعه احاطهگر معمولی | ندارد | نصب خودپرداز با حداقل تعداد | مجموعه احاطهگر مستقل2 | هیچ دو رأس انتخابی مجاور نیستند | خودپردازها در تقاطعهای غیرمجاور (کاهش رقابت) | مجموعه احاطهگر همبند3 | زیرگراف حاصل از رأسهای انتخابی همبند است | امکان ارتباط بین خودپردازها برای انتقال پول |
چالشهای مفهومی
سوال ۱: آیا همیشه یک مجموعه احاطهگر وجود دارد؟ اگر گراف هیچ یالی نداشته باشد چه؟
پاسخ: بله، در هر گرافی خود مجموعه $V$ (همه رأسها) یک مجموعه احاطهگر است. در گراف بدون یال (مجموعهٔ نقاط تنها)، تنها راه پوشش این است که هر رأس خود عضو مجموعه باشد، بنابراین مجموعه احاطهگر برابر با همهٔ رأسها خواهد بود.
پاسخ: بله، در هر گرافی خود مجموعه $V$ (همه رأسها) یک مجموعه احاطهگر است. در گراف بدون یال (مجموعهٔ نقاط تنها)، تنها راه پوشش این است که هر رأس خود عضو مجموعه باشد، بنابراین مجموعه احاطهگر برابر با همهٔ رأسها خواهد بود.
سوال ۲: آیا حداقل مجموعه احاطهگر یکتاست؟
پاسخ: نه، معمولاً چندین مجموعه با اندازهٔ حداقل وجود دارد. در مثال شهر ما، هم {B, E} و هم {C, D} هر دو حداقل هستند. طراح سیستم میتواند با توجه به معیارهای ثانویه (مثلاً نزدیکی به مرکز شهر) بهترین را انتخاب کند.
پاسخ: نه، معمولاً چندین مجموعه با اندازهٔ حداقل وجود دارد. در مثال شهر ما، هم {B, E} و هم {C, D} هر دو حداقل هستند. طراح سیستم میتواند با توجه به معیارهای ثانویه (مثلاً نزدیکی به مرکز شهر) بهترین را انتخاب کند.
سوال ۳: آیا مسئلهٔ یافتن حداقل مجموعه احاطهگر همیشه سریع حل میشود؟
پاسخ: برای گرافهای عمومی، این مسئله «انپی-سخت»4 است، یعنی با بزرگ شدن شهر، یافتن جواب بهینه نیاز به زمان بسیار زیادی دارد. اما برای گرافهای خاص (مانند درختها یا گرافهای مسیر) الگوریتمهای سریعی وجود دارد. در عمل، برای شهرهای واقعی از روشهای تقریبی یا هوشمند استفاده میشود.
پاسخ: برای گرافهای عمومی، این مسئله «انپی-سخت»4 است، یعنی با بزرگ شدن شهر، یافتن جواب بهینه نیاز به زمان بسیار زیادی دارد. اما برای گرافهای خاص (مانند درختها یا گرافهای مسیر) الگوریتمهای سریعی وجود دارد. در عمل، برای شهرهای واقعی از روشهای تقریبی یا هوشمند استفاده میشود.
کاربردهای فراتر از خودپرداز
مسئله مجموعه احاطهگر فقط به خودپرداز محدود نمیشود. در دنیای واقعی، مثالهای متعددی وجود دارد:- دوربینهای مداربسته: نصب حداقل دوربین در تقاطعها به طوری که هر خیابان یا تقاطع زیر نظر باشد.
- ایستگاههای آتشنشانی: هر منطقهٔ شهری یا باید ایستگاه آتشنشانی داشته باشد یا در همسایگی منطقهای که ایستگاه دارد.
- حسگرهای بیسیم در شبکههای حسگر: هر گره حسگر یا خود فعال است یا در محدودهٔ یک گره فعال قرار دارد.
- تخصیص سرور در شبکههای کامپیوتری: هر کامپیوتر یا خود سرور است یا به یک سرور متصل میشود.
جمعبندی: در این مقاله دیدیم که چگونه نقشهٔ یک شهر را به یک گراف تبدیل کنیم و مسئلهٔ مکانیابی حداقل خودپردازها را به یافتن «مجموعه احاطهگر با حداقل اندازه» تقلیل دهیم. با مثال عددی گامبهگام، روش یافتن این مجموعه را تمرین کردیم. همچنین دریافتیم که این مسئله در حالت کلی پیچیده (انپی-سخت) است اما کاربردهای گستردهای در مکانیابی تجهیزات شهری، شبکههای حسگر و امنیت دارد. درک این مفهوم به دانشآموزان کمک میکند تا قدرت مدلسازی ریاضی را در حل مسائل روزمرهٔ شهرنشینی ببینند.
پاورقی
1 گراف (Graph): ساختاری ریاضی متشکل از رأسها (نقاط) و یالها (اتصالات بین آنها) برای مدلسازی روابط زوجی.2 مجموعه احاطهگر مستقل (Independent Dominating Set): مجموعه احاطهگری که هیچ دو رأس آن مجاور (متصل توسط یال) نباشند.
3 مجموعه احاطهگر همبند (Connected Dominating Set): مجموعه احاطهگری که زیرگراف حاصل از رأسهای آن، یک تکه (همبند) باشد.
4 انپی-سخت (NP-hard): دستهای از مسائل که حل دقیق و سریع آنها با بزرگ شدن ابعاد، غیرممکن (یا بسیار دشوار) فرض میشود.
