ماکزیمم درجهٔ گراف: بزرگترین درجهٔ رأسها
تعریف درجه رأس و ماکزیمم درجه در گراف
در نظریه گراف، یک گراف G از مجموعهای از رأسها (نقاط) و یالها (خطهای رابط) تشکیل شده است. به تعداد یالهایی که به یک رأس متصل میشوند، «درجهٔ آن رأس» میگویند. اگر گراف جهتدار باشد، بین درجه ورودی (تعداد یالهای وارد به رأس) و درجه خروجی (تعداد یالهای خارج از رأس) تمایز قائل میشویم.
مثال عملی: فرض کنید کلاسی با 5 دانشآموز دارید و بین هر دو دانشآموزی که با هم دوست هستند، یک خط ارتباط رسم میکنید. اگر دانشآموز «علی» با 3 نفر دیگر دوست باشد، درجه رأس مربوط به علی برابر 3 است. ماکزیمم درجهٔ گراف، بزرگترین تعداد دوستیهایی است که یک دانشآموز در کلاس دارد.
در گراف ساده (بدون حلقه و یال موازی)، درجه هر رأس حداکثر میتواند برابر n-1 باشد که n تعداد کل رأسهاست. بنابراین ماکزیمم درجه همیشه از تعداد رأسها منهای یک کوچکتر یا مساوی است.
انواع گراف و محاسبه ماکزیمم درجه
| نوع گراف | نحوه محاسبه ماکزیمم درجه | مثال عددی |
|---|---|---|
| گراف ساده بدون جهت | بیشترین تعداد یال متصل به هر رأس | گراف با 6 رأس و ماکزیمم درجه 4 |
| گراف جهتدار | ماکزیمم (درجه ورودی، درجه خروجی) یا مجموع آنها | درجه ورودی ماکزیمم 3، خروجی 2 ← Δ=3 |
| گراف کامل $ K_n $ | هر رأس به همه رأسهای دیگر متصل است | Δ = n-1 (مثال: n=5 → Δ=4) |
قضیه دست دادن و رابطه با ماکزیمم درجه
یکی از قضایای بنیادین نظریه گراف، «قضیه دست دادن» است که میگوید مجموع درجههای همه رأسها برابر دو برابر تعداد یالهاست:
از این رابطه نتیجه میشود که مجموع درجهها همواره عددی زوج است. همچنین اگر ماکزیمم درجه را با $ \Delta $ نشان دهیم، آنگاه:
یعنی ماکزیمم درجه حداقل برابر میانگین درجهٔ رأسهاست. این نامساوی در تحلیل تراکم شبکهها بسیار کاربردی دارد.
کاربرد عملی: شناسایی پرطرفدارترین کاربر در شبکه اجتماعی
فرض کنید شبکه اجتماعی کوچکی با 7 کاربر داریم. یالها نشاندهنده رابطه «دنبال کردن» هستند (جهتدار). درجه خروجی هر کاربر تعداد افرادی است که او دنبال میکند و درجه ورودی تعداد دنبالکنندگان اوست. ماکزیمم درجه ورودی، محبوبترین کاربر را مشخص میکند. اگر یک کاربر دارای درجه ورودی 6 باشد (یعنی همه او را دنبال میکنند) ماکزیمم درجهٔ گراف حداکثر 6 خواهد بود. این مفهوم در طراحی الگوریتمهای پیشنهاد دوست و تشخیص افراد تأثیرگذار در شبکههای اجتماعی کاربرد دارد.
چالشهای مفهومی
خیر، در گراف ساده بدون حلقه، هر رأس حداکثر میتواند به n-1 رأس دیگر متصل شود. بنابراین ماکزیمم درجه حداکثر n-1 است. در گراف با حلقه (رأس به خودش متصل شود) هر حلقه معمولاً 2 واحد به درجه اضافه میکند، اما باز هم در گرافهای ساده معمولاً حلقه مجاز نیست.
اگر $ \Delta(G)=0 $، آنگاه همه رأسها درجه صفر دارند، یعنی هیچ یالی در گراف وجود ندارد. چنین گرافی را «گراف تهی» مینامند که فقط شامل رأسهای مجزا و بدون ارتباط است.
خیر. طبق قضیه دست دادن، مجموع درجهها همیشه زوج است. ماکزیمم درجه هر عددی میتواند باشد، اما مجموع درجهها (که حاصل جمع درجه همه رأسهاست) همواره زوج خواهد بود. مثلاً اگر Δ=8 باشد، باز هم مجموع درجهها زوج است.
جمعبندی
پاورقی
1 شبکه اجتماعی (Social Network): ساختاری متشکل از گرهها (افراد یا سازمانها) و یالها (روابط یا تعاملات) که برای مدلسازی ارتباطات در جوامع انسانی و دیجیتال استفاده میشود.
2 رنگآمیزی گراف (Graph Coloring): روشی برای اختصاص رنگ به رأسهای گراف به طوری که هیچ دو رأس مجاور همرنگ نباشند. کمترین تعداد رنگ مورد نیاز را عدد رنگی گراف مینامند و همواره از ماکزیمم درجه به اضافه یک بیشتر نیست.