مجموعهٔ احاطهگر مینیمم گراف (γ)
تعریف اصلی و آشنایی با احاطهگری در گراف
فرض کنید یک گراف2 داریم که شامل مجموعهای از نقطهها (رأسها) و یالهایی است که برخی از این نقطهها را به هم وصل میکند. یک رأس میتواند همسایههای خود را «احاطه» کند. به زبان ساده، اگر در یک گراف، تعدادی از رأسها را انتخاب کنیم به طوری که هر رأس دیگر گراف یا خودِ عضو منتخب باشد یا با یکی از اعضای منتخب همسایه باشد، به آن مجموعه، مجموعهٔ احاطهگر میگوییم.
هدف ما پیداکردن مجموعهٔ احاطهگر با کمترین تعداد عضو است. به این مجموعه، مجموعهٔ احاطهگر مینیمم میگوییم و تعداد اعضای آن را عدد احاطهگر مینامیم و با $ \gamma(G) $ نمایش میدهیم.
چگونه مجموعهٔ احاطهگر مینیمم را پیدا کنیم؟
یافتن مجموعهٔ احاطهگر مینیمم برای گرافهای بزرگ کار دشواری است. اما برای گرافهای کوچک میتوانیم با دقت و بررسی همهٔ حالتها (روش آزمون و خطا) آن را پیدا کنیم. در زیر، مراحل گامبهگام برای یک گراف مشخص را نشان میدهیم.
۱- گراف خود را رسم کنید و همهٔ رأسها را نامگذاری کنید.
۲- از کوچکترین اندازهٔ ممکن (مثلاً یک رأس) شروع کنید. بررسی کنید آیا آن رأس به تنهایی همهٔ رأسها را احاطه میکند؟ (یعنی هر رأس دیگر با آن همسایه باشد یا خودش باشد.)
۳- اگر پاسخ خیر است، اندازه را یکی افزایش دهید و همهٔ ترکیبهای ممکن با آن اندازه را امتحان کنید تا مجموعهای بیابید که شرط احاطهگری را برآورده کند.
۴- اولین اندازهای که برای آن چنین مجموعهای یافت شود، عدد $ \gamma(G) $ خواهد بود.
به عنوان مثال، گراف چهارضلعی (چرخه با $ 4 $ رأس) را در نظر بگیرید. اگر دو رأس غیرهمسایه را انتخاب کنیم، هر دو رأس باقیمانده با این دو رأس همسایه هستند. بنابراین $ \gamma(C_4) = 2 $. با یک رأس نمیتوان همه را پوشش داد، چون هر رأس فقط دو همسایه دارد و یک رأس دیگر را دور میگذارد.
مقایسهٔ عدد احاطهگر برای گرافهای شناخته شده
| نوع گراف | نماد | عدد احاطهگر ($ \gamma $) | توضیح |
|---|---|---|---|
| گراف کامل با $ n $ رأس | $ K_n $ | $ 1 $ | یک رأس همه را میپوشاند |
| مسیر با $ n $ رأس | $ P_n $ | $ \lceil \frac{n}{3} \rceil $ | انتخاب رأسهای دوم، پنجم، ... |
| چرخه با $ n $ رأس | $ C_n $ | $ \lceil \frac{n}{3} \rceil $ | مشابه مسیر با احاطهٔ مدور |
| گراف تهی (بدون یال) با $ n $ رأس | $ \overline{K_n} $ | $ n $ | هر رأس فقط خودش را میپوشاند |
کاربرد عملی: نصب دوربینهای مداربسته در یک موزه
فرض کنید پلان یک موزه به صورت گرافی طراحی شده که هر اتاق یک رأس است و اگر بین دو اتاق یک راهرو (گذر مستقیم) وجود داشته باشد، بین رأسها یال قرار دارد. ما میخواهیم کمترین تعداد دوربین را در اتاقها نصب کنیم به طوری که هر اتاق یا خودش دوربین داشته باشد یا حداقل با یک اتاق دارای دوربین مجاور باشد (یعنی از آن اتاق قابل دید باشد). این دقیقاً همان مسئلهٔ یافتن مجموعهٔ احاطهگر مینیمم است.
برای یک موزه با $ 7 $ اتاق که به شکل یک مسیر $ v_1 - v_2 - \dots - v_7 $ چیده شدهاند، عدد احاطهگر برابر $ \lceil 7/3 \rceil = 3 $ است. با انتخاب اتاقهای $ v_2, v_5 $ و $ v_7 $ همهٔ اتاقها پوشش داده میشوند. این راهکار به مدیر موزه کمک میکند تا هزینهٔ تجهیزات را بهینه کند.
چالشهای مفهومی در درک مجموعهٔ احاطهگر مینیمم
پاسخ: خیر. مجموعهٔ احاطهگر مینیمم میتواند شامل دو رأس مجاور (همسایه) باشد. برای نمونه، در یک مسیر $ P_4 $ با رأسهای $ a-b-c-d $، مجموعهٔ $ \{b,c\} $ احاطهگر است و دو عضو مجاور دارد. اما تعداد اعضای آن مینیمم است (چون با یک رأس نمیتوان همه را پوشاند).
پاسخ: خیر. در گراف تهی (بدون یال)، هر رأس فقط خودش را میپوشاند، بنابراین $ \gamma = n $ که از $ n/2 $ بزرگتر است (برای $ n \ge 1 $). اما در بسیاری از گرافهای همبند، این کران برقرار است.
پاسخ: برای گرافهای عمومی، مسئلهٔ پیدا کردن مجموعهٔ احاطهگر مینیمم یک مسئلهٔ انپی-سخت4 است. یعنی الگوریتم معروفی که همیشه در زمان معقول جواب دقیق بدهد، وجود ندارد (مگر اینکه در نظریهٔ پیچیدگی تحولی رخ دهد). اما برای گرافهای خاص (درختها، مسیرها، چرخهها) الگوریتمهای کارا داریم.
جمعبندی
پاورقی
1 نظریهٔ گراف (Graph Theory): شاخهای از ریاضیات که به مطالعهٔ رابطههای دودویی بین اشیاء با استفاده از ساختارهای نقطه و خط میپردازد.
2 گراف (Graph): یک ساختار شامل مجموعهٔ رأسها (نقاط) و مجموعهٔ یالها (خطوط) که اتصال بین رأسها را نشان میدهد.
3 مجموعهٔ مستقل (Independent Set): مجموعهای از رأسها که هیچ دو رأس آن با یک یال به هم متصل نباشند.
4 انپی-سخت (NP-Hard): دستهای از مسائل که حل آنها حداقل به اندازهٔ حل مسائل انپی (غیرقطعی چندجملهای) دشوار است و الگوریتم سریعی برای آنها شناخته نشده است.
