عدد احاطهگری گراف γ(G) : کوچکترین تیم مراقبِ رئوس
مجموعه احاطهگر و عدد احاطهگری: تعاریف پایه
فرض کنید یک گراف1 ساده و بدون جهت داریم که از رأسها2 و یالها3 تشکیل شده است. یک مجموعه از رأسها را «مجموعه احاطهگر» مینامیم اگر هر رأس گراف یا خودش عضو این مجموعه باشد یا حداقل با یکی از اعضای این مجموعه همسایه باشد. به عبارت دیگر، مجموعه احاطهگر مانند یک «تیم مراقب» عمل میکند که هر نقطه از گراف یا خود مراقب است یا در تماس مستقیم با یک مراقب قرار دارد.
عدد احاطهگری که با γ(G) نشان داده میشود، برابر با اندازه (تعداد اعضای) کوچکترین مجموعه احاطهگر است. به چنین مجموعهای «مجموعه احاطهگر مینیمم» میگوییم. توجه کنید که ممکن است چندین مجموعه احاطهگر مینیمم متفاوت وجود داشته باشد، اما تعداد اعضای آنها یکسان و برابر γ(G) است.
محاسبه گامبهگام عدد احاطهگری در گرافهای ساده
برای محاسبه γ(G) مراحل زیر را طی میکنیم:
- تمام رأسها را فهرست کنید.
- مجموعههای کوچکی از رأسها را امتحان کنید (از کوچک به بزرگ) تا اولین مجموعهای را بیابید که تمام رأسها را احاطه کند.
- اندازه آن مجموعه، عدد احاطهگری است.
مثال ۱: گراف مسیر4 با 4 رأس را در نظر بگیرید که به صورت خطی v1 — v2 — v3 — v4 متصل شدهاند. مجموعه {v2, v4} یک مجموعه احاطهگر است؟ رأس v1 با v2 مجاور است، v2 خودش عضو است، v3 با v2 و v4 مجاور است، v4 خودش عضو است. بنابراین همه رأسها پوشش داده شدند. آیا مجموعه با اندازه 1 میتواند احاطهگر باشد؟ خیر، زیرا یک رأس حداکثر خودش و همسایگانش (حداکثر دو رأس دیگر در مسیر) را پوشش میدهد و به هر حال یک رأس بیپوشش میماند. پس γ = 2.
| نوع گراف | تعداد رأسها (n) | عدد احاطهگری γ(G) | توضیح |
|---|---|---|---|
| گراف کامل5K_n | n | 1 | یک رأس با همه همسایه است |
| مسیر P_n | n | \lceil n/3 \rceil | انتخاب هر رأس سوم |
| چرخه6C_n | n \ge 3 | \lceil n/3 \rceil | مشابه مسیر با احاطه دورانی |
| گراف پوچ (بدون یال) | n | n | هر رأس فقط خودش را میپوشاند |
کاربرد عملی: مکانیابی بهینه حسگرها در یک شبکه بیسیم
فرض کنید در یک ساختمان با 10 اتاق (رأس) میخواهیم حسگرهای دود نصب کنیم. هر حسگر اگر در اتاقی نصب شود، علاوه بر اتاق خود، اتاقهای مجاور (متصل به یک راهرو) را نیز پوشش میدهد. کمترین تعداد حسگر مورد نیاز همان عدد احاطهگری گراف همجواری اتاقهاست. اگر اتاقها به شکل یک مسیر خطی باشند، با نصب حسگر در اتاقهای شماره 2، 5 و 8 (طبق فرمول $ \lceil 10/3 \rceil = 4 $) همه اتاقها پوشش داده میشوند. به این ترتیب در هزینهها صرفهجویی میشود.
مثال دیگر در شبکههای اجتماعی است: میخواهیم حداقل افراد تأثیرگذار را انتخاب کنیم تا همه افراد شبکه یا خودشان انتخاب شده باشند یا با یک فرد تأثیرگذار دوست باشند. این عدد تأثیرگذاری همان عدد احاطهگری گراف دوستی است.
چالشهای مفهومی در عدد احاطهگری
۱. آیا هر مجموعه احاطهگر مینیمم، کوچکترین مجموعه از نظر تعداد اعضاست؟
پاسخ: بله، دقیقاً به همین دلیل به آن «مینیمم» میگوییم. اما واژه «مینیمال» با «مینیمم» تفاوت دارد. مجموعه احاطهگر «مینیمال» مجموعهای است که با حذف هر یک از اعضایش، خاصیت احاطهگری از بین برود. یک مجموعه مینیمم همیشه مینیمال است، اما عکس آن لزوماً برقرار نیست. در حقیقت عدد احاطهگری اندازه کوچکترین مجموعه در میان تمام مجموعههای مینیمال است.
۲. چگونه عدد احاطهگری یک گراف با n رأس میتواند بیشتر از n/2 باشد؟
پاسخ: بله، برای گراف پوچ (بدون یال) داریم γ = n که به مراتب از n/2 بیشتر است. در گرافهایی با یالهای کم، برای احاطه کردن همه رأسها چارهای جز انتخاب اکثر آنها نیست. به عنوان مثال، در گرافی که به شکل دو ستاره مجزا است، ممکن است مجبور شوید بیش از نیمی از رأسها را انتخاب کنید.
۳. آیا همیشه میتوانیم عدد احاطهگری را سریع محاسبه کنیم؟
پاسخ: متأسفانه خیر. مسئله یافتن عدد احاطهگری برای گرافهای عمومی یک مسئله انپی-سخت7 است، یعنی الگوریتم سریع و کارآمدی (با زمان چندجملهای) برای آن شناخته نشده است. برای گرافهای خاص مانند مسیر، چرخه، درخت و گرافهای دوبخشی میتوان با روشهای پویا آن را یافت، اما برای یک گراف دلخواه با تعداد رأس زیاد، محاسبه دقیق بسیار زمانبر است.
پاورقی
1 گراف (Graph): ساختاری متشکل از رأسها و یالها که روابط زوجی بین رأسها را نشان میدهد.2 رأس (Vertex): یک نقطه یا گره در گراف که نشاندهنده یک شیء یا موقعیت است.
3 یال (Edge): ارتباط بین دو رأس در گراف که به صورت خط یا کمان نمایش داده میشود.
4 مسیر (Path): گرافی است که رأسهای آن در یک خط قرار گرفته و هر رأس به دو همسایه (به جز دو سر) متصل است.
5 گراف کامل (Complete Graph): گرافی که در آن هر دو رأس متمایز با یک یال به هم متصل هستند.
6 چرخه (Cycle): گرافی که رأسهای آن در یک حلقه بسته به هم متصل شدهاند و هر رأس دقیقاً دو همسایه دارد.
7 انپی-سخت (NP-Hard): دستهای از مسائل که حداقل به اندازه دشوارترین مسائل کلاس NP هستند و الگوریتم سریع برای آنها وجود ندارد (تا کنون).