حداکثر احاطه یک رأس: در گرافی با ماکزیمم درجهٔ Δ، حداکثر Δ + 1 رأس
۱. آشنایی با مفاهیم پایه: رأس، یال، درجه و ماکزیمم درجه
در نظریهٔ گراف، یک گراف از مجموعهای از رأسها (نقاط) و یالها (خطهای رابط) تشکیل میشود. اگر دو رأس با یک یال به هم متصل باشند، آنها را همسایه یکدیگر مینامیم. برای یک رأس مانند v، تعداد همسایههای آن را درجهٔ رأس میگوییم و با deg(v) نمایش میدهیم. همچنین ماکزیمم درجهٔ گراف که آن را با Δ (دلتای بزرگ) نشان میدهیم، بزرگترین درجه در میان همهٔ رأسهای گراف است.
فرض کنید در یک گراف ساده1 (بدون یال موازی و بدون حلقه)، به دنبال این هستیم که یک رأس خاص حداکثر چند رأس دیگر را میتواند «احاطه» کند. منظور از احاطه، شامل خود آن رأس و همهٔ همسایههای مستقیم آن است. اگر درجهٔ یک رأس برابر d باشد، آنگاه مجموعهٔ احاطهگر آن رأس شامل خودش و d همسایه میشود؛ بنابراین اندازهٔ این مجموعه برابر d + 1 خواهد بود.
۲. کران بالای احاطه: اثبات قضیهٔ Δ + 1
حال به اصل مطلب میرسیم: «در هر گرافی با ماکزیمم درجهٔ Δ، حداکثر تعداد رأسهایی که میتوانند توسط یک رأس احاطه شوند (یعنی خود آن رأس به اضافهٔ همسایههایش) برابر Δ + 1 است.» این یک قضیهٔ ساده اما بنیادین است. برای اثبات، فرض کنید v رأس دلخواهی در گراف باشد. درجهٔ آن حداکثر برابر Δ است، زیرا Δ بزرگترین درجه در کل گراف است. پس deg(v) \le Δ. مجموعهٔ رأسهای احاطهشده توسط v برابر \{v\} \cup N(v) است که در آن N(v) مجموعهٔ همسایههای v است. اندازهٔ این مجموعه برابر 1 + |N(v)| = 1 + deg(v) \le 1+Δ. بنابراین هیچ رأسای نمیتواند بیش از Δ+1 رأس را احاطه کند. برای رسیدن به تساوی، باید رأسای با درجهٔ دقیقاً Δ انتخاب شود و گراف نیز ساده باشد.
برای درک بهتر، جدول زیر مقایسهٔ سه گراف مختلف با ماکزیمم درجههای متفاوت را نشان میدهد. در هر گراف، یک رأس با بیشترین درجه را انتخاب کردهایم و اندازهٔ مجموعهٔ احاطهگر آن را محاسبه کردهایم.
| نوع گراف | ماکزیمم درجه (Δ) | درجهٔ رأس منتخب (d) | اندازهٔ احاطه (d+1) | کران Δ+1 |
|---|---|---|---|---|
| مسیر با ۳ رأس (P3) | 2 | 2 | 3 | 3 |
| گراف کامل K4 | 3 | 3 | 4 | 4 |
| ستارهٔ K1,5 | 5 | 5 | 6 | 6 |
۳. کاربرد عملی در مسائل بهینهسازی شبکه
این قضیه در طراحی شبکههای مخابراتی و کامپیوتری کاربرد دارد. فرض کنید هر رأس یک ایستگاه مخابراتی است و یالها نشاندهندهٔ ارتباط مستقیم هستند. اگر بخواهیم پیامی را از یک ایستگاه به همهٔ ایستگاههای درون محدودهٔ احاطهٔ آن (خودش و همسایههای یکگامه) برسانیم، حداکثر تعداد ایستگاههایی که تحت پوشش قرار میگیرند، از Δ+1 تجاوز نمیکند. به عبارت دیگر، هر ایستگاه بدون نیاز به اطلاعات از کل شبکه، میتواند بداند که حداکثر چه تعداد گره دیگر را میتواند مستقیماً تحت تأثیر قرار دهد.
مثال دیگر در الگوریتمهای مسیریابی است: اگر یک رأس بخواهد لیست همسایههای خود را به روز کند، حافظهٔ مورد نیاز از مرتبهٔ O(Δ) خواهد بود که بسیار کارآمد است. این کران ساده، پایهای برای قضیههای پیچیدهتر مانند قضیهٔ بروکس2 در رنگآمیزی گراف است.
۴. چالشهای مفهومی
۱. آیا ممکن است عدد احاطه از Δ+1 بیشتر شود اگر گراف دارای یال موازی یا حلقه باشد؟
پاسخ: بله. اگر گراف دارای حلقه (لطفی که رأس را به خودش وصل کند) باشد، آن رأس در احاطهٔ خودش دو بار شمرده نمیشود (چون مجموعه است) اما مفهوم درجه تغییر میکند. در گرافهای با یال موازی، درجهٔ رأس میتواند از تعداد همسایههای متمایز بیشتر باشد، اما در تعریف احاطه، فقط رأسهای متمایز اهمیت دارند. در گراف ساده، کران Δ+1 محکم است.
۲. اگر ماکزیمم درجهٔ گراف Δ باشد، آیا همیشه رأسای وجود دارد که دقیقاً Δ+1 رأس را احاطه کند؟
پاسخ: خیر. برای وجود چنین رأسی، باید رأسی با درجهٔ دقیقاً Δ وجود داشته باشد و گراف ساده باشد. همیشه چنین رأسی وجود دارد (طبق تعریف ماکزیمم درجه) چون Δ بزرگترین درجه است و حداقل یک رأس به آن درجه میرسد. بنابراین در گراف ساده، همیشه میتوان رأس احاطهگر با اندازهٔ Δ+1 یافت.
۳. آیا این قضیه برای گرافهای جهتدار نیز برقرار است؟
پاسخ: در گرافهای جهتدار، مفهوم درجه به دو بخش درجهٔ ورودی و خروجی تقسیم میشود. اگر ماکزیمم درجهٔ خروجی را Δ^+ در نظر بگیریم، آنگاه یک رأس میتواند حداکثر Δ^+ + 1 رأس (خودش و همسایههای خروجی) را احاطه کند. اما اگر جهت یالها مهم نباشد و گراف زمینهای بدون جهت در نظر گرفته شود، همان کران قبلی برقرار است.
۵. جمعبندی
۶. پاورقی
1 گراف ساده (Simple Graph): گرافی بدون یال موازی (چند یال بین یک جفت رأس) و بدون حلقه (یالی که یک رأس را به خودش وصل کند).
2 قضیهٔ بروکس (Brooks' Theorem): قضیهای در رنگآمیزی گراف که بیان میکند عدد رنگی یک گراف همبند حداکثر برابر ماکزیمم درجه است، مگر در گرافهای کامل و دورهای فرد که عدد رنگی برابر Δ+1 میشود.