احاطهگری در گراف Cₙ: تعیین کمترین رأسها برای پوشش دور n رأسی
گراف چرخهای چیست و مسئله احاطهگری چگونه تعریف میشود؟
گراف چرخهای با نماد $C_n$ نشان داده میشود و از $n$ رأس تشکیل شده است که به صورت یک حلقه بسته به هم متصل هستند. به بیان ساده، میتوانید $n$ نقطه را روی یک دایره تصور کنید که هر نقطه فقط به دو همسایه خود (یکی در جهت عقربههای ساعت و یکی در خلاف آن) متصل است. این گرافها در مباحث نظریه گراف1 از پایهایترین ساختارها هستند.
مسئله احاطهگری2 به این پرسش پاسخ میدهد: کمترین تعداد رأسهایی که باید انتخاب کنیم تا هر رأس گراف یا خود در مجموعه باشد یا حداقل یک همسایه در آن داشته باشد، چند است؟ به این تعداد، «عدد احاطهگری»3 میگویند و آن را با $\gamma(G)$ نمایش میدهند.
برای درک بهتر، یک مثال ساده بزنیم: فرض کنید در یک مدار بسته از لامپها (رأسها) هر لامپ میتواند خودش و دو لامپ مجاورش را روشن کند. میخواهیم کمترین تعداد لامپ را روشن کنیم تا همه لامپها روشن شوند. این دقیقاً همان مسئله احاطهگری روی گراف چرخهای است.
روش گامبهگام محاسبه عدد احاطهگری برای چرخههای کوچک
برای درک شهودی، بیایید چند چرخه کوچک را بررسی کنیم و با الگوریتم ساده، کمترین رأسهای لازم را بیابیم.
گام اول: برای $C_3$ (مثلث): هر رأس دو همسایه دارد. اگر یک رأس را انتخاب کنیم، خودش و دو همسایهاش (یعنی کل ۳ رأس) پوشش داده میشوند. پس با $1$ رأس کار تمام است. فرمول $\lceil 3/3 \rceil = \lceil 1 \rceil = 1$ درست است.
گام دوم: برای $C_4$ (مربع): اگر یک رأس را برداریم، خودش و دو همسایه (سه رأس) پوشش مییابند اما رأس چهارم (مقابل) پوشیده نمیشود. پس یک رأس کافی نیست. با دو رأس میتوانیم: دو رأس غیرمجاور انتخاب کنیم. مثلاً رأس شماره ۱ و ۳. هر یک، خود و همسایههایش را پوشش میدهد و کل ۴ رأس پوشش مییابد. فرمول $\lceil 4/3 \rceil = \lceil 1.33 \rceil = 2$ درست است.
گام سوم: برای $C_5$ (پنجضلعی): یک رأس فقط ۳ رأس را پوشش میدهد. دو رأس: اگر فاصله آنها ۲ باشد (یک رأس بین آنها)، ممکن است برخی رأسها نپوشند. بهترین حالت انتخاب دو رأس با فاصله ۲ است که هر کدام ۳ رأس را پوشش میدهند اما همپوشانی دارند. برای $n=5$ با دو رأس میتوان همه را پوشاند؟ بله. دو رأس که فقط یک رأس بین آنها فاصله باشد (مثلاً رأسهای ۱ و ۳) کل گراف را میپوشانند. اما بررسی کنید: اگر دو رأس مجاور باشند، رأس مقابل ممکن است نپوشد. بهترین انتخاب نیاز به دقت دارد. فرمول $\lceil 5/3 \rceil = \lceil 1.66 \rceil = 2$. پس دو رأس کافی است.
| نام گراف | تعداد رأسها (n) | عدد احاطهگری γ(Cₙ) | مثال مجموعه احاطهگر |
|---|---|---|---|
| C₃ (مثلث) | 3 | 1 | {۱} |
| C₄ (مربع) | 4 | 2 | {۱,۳} |
| C₅ (پنجضلعی) | 5 | 2 | {۱,۳} |
| C₆ (ششضلعی) | 6 | 2 | {۱,۴} |
| C₇ (هفتضلعی) | 7 | 3 | {۱,۳,۵} |
کاربرد عملی: مکانیابی بهینه ایستگاههای آتشنشانی در یک شهر دایرهای
فرض کنید یک شهر به شکل یک جاده کمربندی دایرهای طراحی شده است. در هر تقاطع (رأس گراف) یک محله قرار دارد. میخواهیم ایستگاههای آتشنشانی را طوری بسازیم که هر محله یا خودش ایستگاه داشته باشد یا در فاصله یک تقاطع با یک ایستگاه (یعنی همسایه بلافصل) قرار گیرد. هر ایستگاه میتواند به محله خود و دو محله مجاور خدمات دهد. کمترین تعداد ایستگاه مورد نیاز برای شهری با $n$ محله برابر است با $\lceil n/3 \rceil$.
مثال: اگر شهر دارای $n=9$ محله باشد، فرمول میگوید $\lceil 9/3 \rceil = 3$ ایستگاه کافی است. با انتخاب محلههای شماره $2,5,8$ (با فاصله ۳ از هم) هر محلهای یا ایستگاه دارد یا حداکثر یک فاصله با ایستگاه بعدی دارد. این الگو در بهینهسازی شبکههای حسگر بیسیم و تخصیص مراکز خدماتی کاربرد گسترده دارد.
چالشهای مفهومی در احاطهگری چرخهها
پاسخ: وقتی $n=3k$، میتوان رأسهای $2,5,8,...,3k-1$ را انتخاب کرد. در این حالت هر رأس انتخابی دقیقاً ۳ رأس (خود و دو همسایه) را پوشش میدهد و هیچ همپوشانیای بین رأسهای پوششیافته توسط دو رأس انتخابی متفاوت وجود ندارد. حداقل بودن نیز از آنجا ثابت میشود که هر رأس انتخابی حداکثر ۳ رأس را پوشش میدهد و برای پوشش $3k$ رأس حداقل $k$ رأس نیاز است. این راه حل یکتا نیست اما الگوی آن یکنواخت است.
پاسخ: بله، بهترین روش برای ساختن مجموعه احاطهگر در چرخه این است که رأسها را با فاصله تقریبی $3$ واحد انتخاب کنیم. برای $n=3k$ فاصله دقیقاً $3$، برای $n=3k+1$ فاصلهها ترکیبی از $3$ و $2$ و برای $n=3k+2$ نیز مشابه. این الگو تضمین میکند که هر رأس پوشیده شود.
پاسخ: در مسیر (گراف خطی) که دو انتها فقط یک همسایه دارند، عدد احاطهگری برابر $\lceil n/3 \rceil$ است اما برای $n \equiv 1 \pmod{3}$ گاهی یک واحد کمتر از چرخه میشود؟ خیر، هر دو یکسان هستند! اما در مسیر برای $n=4$ نیز $\lceil 4/3 \rceil = 2$ که با چرخه برابری میکند. تفاوت اصلی در نحوه چیدمان مجموعه احاطهگر است؛ در چرخه به دلیل دوری بودن، گاهی چیدمان متقارنتر و در مسیر چیدمان از یک انتها شروع میشود.
جمعبندی
پاورقی
1 نظریه گراف (Graph Theory): شاخهای از ریاضیات که به مطالعه گرافها به عنوان ساختارهایی شامل رأس (نقطه) و یال (اتصال بین نقاط) میپردازد.
2 احاطهگری (Dominating Set): مجموعهای از رأسها در یک گراف که هر رأس خارج از مجموعه حداقل یک همسایه درون مجموعه داشته باشد.
3 عدد احاطهگری (Domination Number): کوچکترین اندازه یک مجموعه احاطهگر در گراف که با $\gamma(G)$ نمایش داده میشود.