کران پایین عدد احاطهگری: چرا γ(G) نمیتواند خیلی کوچک باشد؟
عدد احاطهگری چیست و چرا به کران پایین نیاز داریم؟
فرض کنید یک گراف با n رأس داریم. مجموعهای از رأسها را احاطهگر مینامیم اگر هر رأس گراف یا خودش در آن مجموعه باشد یا همسایهای در آن مجموعه داشته باشد. عدد احاطهگری که با نماد $ \gamma(G) $ نشان داده میشود، کوچکترین اندازه (تعداد اعضا) یک مجموعه احاطهگر در گراف G است.
پرسش طبیعی این است که آیا $ \gamma(G) $ میتواند هر قدر که دوست داریم کوچک شود؟ پاسخ خیر است. کران پایین یعنی عددی مانند $ f(n) $ که برای هر گراف با n رأس، داشته باشیم $ \gamma(G) \ge f(n) $. شناخت این کرانها به ما کمک میکند بدون محاسبه دقیق، بفهمیم یک گراف نمیتواند احاطهگری خیلی کوچک داشته باشد.
کران پایین بر مبنای بیشینه درجه: قضیهٔ ساده اما کاربردی
یکی از شناختهشدهترین کرانهای پایین، از درجه رأسها تغذیه میکند. فرض کنید $ \Delta(G) $ بیشینه درجه1 در گراف G باشد. آنگاه میتوان نوشت:
دلیل: هر رأس در مجموعه احاطهگر، حداکثر میتواند خود و همسایگانش را بپوشاند. اگر رأس v در مجموعه احاطهگر باشد، نهایتاً $ \deg(v)+1 $ رأس (خودش به اضافه همسایهها) تحت پوشش قرار میگیرند. از آنجا که بیشینه این مقدار $ \Delta(G)+1 $ است، با k رأس در مجموعه احاطهگر، حداکثر $ k \cdot (\Delta(G)+1) $ رأس پوشیده میشوند. برای پوشش همه n رأس باید $ k \cdot (\Delta(G)+1) \ge n $، پس $ k \ge \frac{n}{\Delta(G)+1} $.
این کران برای گرافهای بدون یال (مجموعهٔ تهی) که $ \Delta(G)=0 $ است، تبدیل به $ \gamma(G) \ge n $ میشود که درست است (چون هر رأس باید خودش در مجموعه باشد).
مقایسه کران پایین در خانوادههای مختلف گراف
هر خانواده از گرافها کران پایین متفاوتی دارد. جدول زیر سه خانواده مهم را با مقدار دقیق $\gamma(G)$ و کران پایین حاصل از فرمول قبلی مقایسه میکند.
| نوع گراف | تعداد رأسها (n) | بیشینه درجه ($\Delta$) | کران پایین $ \frac{n}{\Delta+1} $ | مقدار واقعی $\gamma(G)$ |
|---|---|---|---|---|
| مسیر $P_n$ | n=7 | 2 | 2.33 → 3 | 3 |
| چرخ $W_n$ (با n\ge 4) | n=5 | 4 | 1 | 1 |
| گراف مکعب سهبعدی $Q_3$ | 8 | 3 | 2 | 4 |
همانطور که میبینید، کران $ \frac{n}{\Delta+1} $ یک کران پایین محکم نیست (در مکعب بسیار فاصله دارد) اما همیشه درست است و به سرعت قابل محاسبه است.
کاربرد عملی: یافتن حداقل نگهبانان در یک موزه
فرض کنید یک موزه با 12 تالار داریم که تالارها به صورت یک گراف با درجه حداکثر 3 به هم متصل شدهاند (هر تالار با حداکثر سه تالار دیگر راهرو دارد). مدیر موزه میخواهد حداقل تعداد نگهبان را طوری در تالارها مستقر کند که هر تالار یا خودش نگهبان داشته باشد یا با تالاری که نگهبان دارد همسایه باشد. با استفاده از کران پایین داریم:
بنابراین هر طرحی که کمتر از 3 نگهبان داشته باشد غیرممکن است. این کران، مدیر را از جستجوی بینتیجه برای 1 یا 2 نگهبان بینیاز میکند. بعد از این کران، میتوان با روشهای جستجو، یک مجموعه احاطهگر با اندازه 3 یافت یا ثابت کرد شاید نیاز به 4 نگهبان باشد.
چالشهای مفهومی
چالش 1: آیا همیشه کران $ \frac{n}{\Delta+1} $ به جواب دقیق نزدیک است؟
خیر. برای گراف چرخ $W_5$ این کران برابر 1 است و جواب دقیق هم 1 است (خود رأس مرکزی). اما برای مکعب سهبعدی $Q_3$ کران 2 است در حالی که عدد احاطهگری 4 است. یعنی کران میتواند بسیار سست باشد.
چالش 2: اگر گراف شامل هیچ یالی نباشد، کران پایین چه میشود؟
در گراف تهی ($ \Delta = 0 $)، فرمول $ \gamma(G) \ge \frac{n}{1} = n $ را میدهد. از طرفی یک مجموعه احاطهگر باید همه رأسها را شامل شود چون رأسها هیچ همسایهای ندارند، بنابراین $ \gamma(G) = n $. در اینجا کران دقیق و محکم است.
چالش 3: آیا میتوان کران پایین بهتری از بیشینه درجه یافت؟
بله. کرانهای قویتری وجود دارد، مانند $ \gamma(G) \ge \frac{n}{1+\Delta} $ که همان است، اما اگر به جای $\Delta$ از مجموع درجهها یا میانگین درجه استفاده کنیم، کران میتواند افزایش یابد. یکی از معروفترین کرانها از قضیه کارونا-لیپتون نشأت میگیرد: در گراف بدون رأس تنها (بدون رأس با درجه صفر)، $ \gamma(G) \ge \frac{n}{2\Delta} $ گاهی محکمتر است اما همیشه درست نیست.
پاورقی
2 مجموعه احاطهگر (Dominating Set): مجموعهای از رأسهای گراف که هر رأس دیگر یا خود عضو مجموعه است یا حداقل یک همسایه در آن مجموعه دارد.
3 عدد احاطهگری (Domination Number): کوچکترین اندازه یک مجموعه احاطهگر در گراف که با $ \gamma(G) $ نمایش داده میشود.