احاطهگری در گراف Pₙ: کمترین رأسها برای پوشش یک مسیر
گراف مسیر Pₙ و همسایگی رأسها
گراف مسیر Pₙ به سادگی یک خط راست از n رأس (نقطه) است که رأسهای مجاور با یک یال به هم وصل شدهاند. برای مثال P₄ چهار رأس دارد که به صورت خطی کنار هم قرار گرفتهاند. در نظریه گراف1، مسئله احاطهگری (Dominating Set) به این معناست: میخواهیم تعدادی از رأسها را انتخاب کنیم به طوری که هر رأس دیگر یا خود در مجموعه باشد یا با یکی از رأسهای انتخاب شده همسایه باشد.
برای درک بهتر، یک مسیر ۵ رأسی (P₅) را تصور کنید: رأسها را به ترتیب v₁, v₂, v₃, v₄, v₅ نامگذاری میکنیم. همسایه هر رأس داخلی دو رأس (چپ و راست) است، رأس اول فقط یک همسایه (رأس دوم) و رأس آخر فقط یک همسایه (رأس چهارم). مجموعه احاطهگر باید همه رأسها را پوشش دهد.
عدد احاطهگری γ(Pₙ) و فرمول کلی
عدد احاطهگری (Domination Number) و با نماد γ(G) نشان داده میشود، یعنی اندازه کوچکترین مجموعه احاطهگر در گراف G. برای گراف مسیر Pₙ، یک فرمول ساده و جذاب وجود دارد:
علامت ⌈x⌉ نشان دهنده سقف (بزرگترین عدد صحیح بزرگتر یا مساوی x) است. یعنی به ازای هر n، کافی است تعداد رأسها را بر ۳ تقسیم کنیم و جواب را به سمت بالا گرد کنیم. برای مثال در P₄ داریم ⌈۴/۳⌉ = ⌈۱.۳۳⌉ = ۲ و در P₅ داریم ⌈۵/۳⌉ = ⌈۱.۶۶⌉ = ۲.
برای اثبات این فرمول، یک الگوی ساده وجود دارد: رأسها را به صورت بلوکهای سهتایی در نظر میگیریم و از رأس دوم هر بلوک به عنوان عضو مجموعه احاطهگر استفاده میکنیم. این روش همواره کمترین تعداد را میدهد. در ادامه جدول مقادیر γ(Pₙ) برای nهای مختلف آورده شده است.
| تعداد رأسها (n) | عدد احاطهگری γ(Pₙ) | یک مجموعه احاطهگر مینیمال (شاخص رأسها) |
|---|---|---|
| 1 | 1 | {v₁} |
| 2 | 1 | {v₁} |
| 3 | 1 | {v₂} |
| 4 | 2 | {v₂, v₄} |
| 5 | 2 | {v₂, v₅} |
| 6 | 2 | {v₂, v₅} |
| 7 | 3 | {v₂, v₅, v₇} |
| 8 | 3 | {v₂, v₅, v₈} |
الگوریتم گام به گام برای یافتن مجموعه احاطهگر مینیمال در مسیر
روش ساخت مجموعه احاطهگر با اندازه ⌈n/3⌉ بسیار ساده است:
گام اول: رأسها را از چپ به راست با اعداد 1,2,...,n شمارهگذاری کنید.
گام دوم: رأس شماره ۲ را انتخاب کنید. این رأس، خودش و همسایههایش (رأسهای ۱ و ۳) را پوشش میدهد.
گام سوم: سه گام به جلو بروید: از رأس ۲ به رأس ۵ میرویم و آن را انتخاب میکنیم (چون رأسهای ۴,۵,۶ را پوشش میدهد).
گام چهارم: این روند را ادامه دهید تا به انتهای مسیر برسید. اگر در انتها یک یا دو رأس باقی ماندند، بسته به موقعیت، آخرین انتخاب را تنظیم کنید.
برای مثال در P₉ داریم: انتخاب رأسهای ۲,۵,۸. این سه رأس، همه n=9 رأس را پوشش میدهند و ⌈۹/۳⌉ = ۳.
کاربرد عملی: مسئله پوشش دوربینهای مداربسته در یک راهرو
فرض کنید راهرویی به طول n متر داریم که هر متر آن یک نقطه حساس است. یک دوربین نصب شده در هر نقطه، علاوه بر خود آن نقطه، نقاط مجاور (چپ و راست) را نیز پوشش میدهد. مدیر ساختمان میخواهد کمترین تعداد دوربین را نصب کند به طوری که همه نقاط راهرو پوشش داده شوند. این دقیقاً همان مسئله عدد احاطهگری در Pₙ است.
برای یک راهرو n=7 متری، طبق فرمول به ⌈۷/۳⌉ = ۳ دوربین نیاز داریم. با الگوریتم بالا دوربینها را در مترهای ۲,۵,۷ نصب میکنیم. بررسی کنید: نقطه ۱ توسط دوربین ۲، نقطه ۲ خودش، نقطه ۳ توسط ۲، نقطه ۴ توسط ۵، نقطه ۵ خودش، نقطه ۶ توسط ۵ یا ۷، نقطه ۷ خودش. همه نقاط پوشیده شدهاند. مشاهده میکنید که با ۲ دوربین امکانپذیر نبود (چرا که حداکثر هر دوربین ۳ نقطه را پوشش میدهد و ۲ دوربین حداکثر ۶ نقطه را پوشش میدهند).
چالشهای مفهومی
۱) آیا همیشه مجموعه احاطهگر منحصربهفردی برای مسیر وجود دارد؟
خیر. اغلب مسیرها چندین مجموعه احاطهگر مینیمال متفاوت دارند. مثلاً برای P₆، هم {v₂, v₅} و هم {v₂, v₄} و هم {v₁, v₄} جواب میدهند. اما همه آنها اندازه ۲ دارند.
۲) چرا فرمول ⌈n/3⌉ برای مسیر صحیح است و مثلاً ⌈n/2⌉ نیست؟
چون هر رأس انتخاب شده، حداکثر میتواند خودش و دو همسایه مستقیمش (در مجموع سه رأس) را پوشش دهد. بنابراین با k رأس حداکثر ۳k رأس پوشش داده میشود. برای پوشش n رأس باید ۳k ≥ n یا k ≥ n/3 و چون تعداد رأسها صحیح است، k ≥ ⌈n/3⌉. با ارائه یک الگو نشان میدهیم که این حد قابل دستیابی است.
۳) اگر به جای پوشش همسایههای مجاور، پوشش تا فاصله ۲ را در نظر بگیریم، فرمول چگونه تغییر میکند؟
این مسئله به «احاطهگری k-ام» معروف است. برای فاصله ۲، هر رأس تا ۵ رأس را پوشش میدهد و فرمول به ⌈n/5⌉ تغییر میکند. اما در همین مقاله فقط حالت پایه (همسایگی بلافصل) را بررسی میکنیم.
پاورقی
1 نظریه گراف (Graph Theory): شاخهای از ریاضیات که به مطالعه گرافها به عنوان ساختارهایی متشکل از رأس (گره) و یال (پیوند) میپردازد.
2 مجموعه احاطهگر (Dominating Set): مجموعهای از رأسها در یک گراف به طوری که هر رأس دیگر یا خود در مجموعه باشد یا با حداقل یک عضو از آن مجموعه همسایه باشد.
3 عدد احاطهگری (Domination Number): اندازه کوچکترین مجموعه احاطهگر در یک گراف که با γ(G) نشان داده میشود.