ماکزیمم درجهٔ گراف Δ(G)

بروزرسانی شده در: 17:33 1405/02/17 مشاهده: 17 دسته بندی: کپسول آموزشی

ماکزیمم درجهٔ گراف (Δ(G))

آشنایی با بزرگترین تعداد یال‌های متصل به یک رأس، مفاهیم پایه، مثال‌ها و کاربردها در نظریهٔ گراف

در نظریهٔ گراف، ماکزیمم درجه که با نماد Δ(G) نشان داده می‌شود، بیانگر بیشترین تعداد یال‌هایی است که به یک رأس در گراف G متصل هستند. این مفهوم نقش کلیدی در تحلیل ساختار گراف، الگوریتم‌های مسیریابی، شبکه‌های ارتباطی و قضایای مهمی مانند قضیهٔ هندزلیل¹ دارد. در این مقاله با زبانی ساده و مثال‌های متنوع، نحوهٔ محاسبه، ویژگی‌ها و کاربردهای ماکزیمم درجه را مرور می‌کنیم.

تعریف ماکزیمم درجه و نمادگذاری

در یک گراف بدون جهت²، درجهٔ هر رأس برابر تعداد یال‌هایی است که به آن رأس متصل می‌شوند. اگر گراف دارای حلقه³ باشد، هر حلقه معمولاً به عنوان دو واحد درجه محاسبه می‌شود. ماکزیمم درجه که آن را با Δ(G) نمایش می‌دهیم، بزرگترین درجه در میان همهٔ رأس‌های گراف است. به عبارت ساده‌تر، اگر در یک شبکه دوستی، ببینیم کدام شخص بیشترین دوستان را دارد، تعداد دوستان آن شخص همان ماکزیمم درجه است.

$ \Delta(G) = \max_{v \in V(G)} \deg(v) $ که $V(G)$ مجموعهٔ رأس‌ها و $\deg(v)$ درجهٔ رأس $v$ است.

برای نمونه، گرافی با 4 رأس در نظر بگیرید که به شکل یک مربع کامل (چهار ضلعی با دو قطر) کشیده شده است: هر رأس به سه رأس دیگر متصل است، بنابراین $\deg(v)=3$ برای همهٔ رأس‌ها و $\Delta(G)=3$. در یک گراف خطی با 5 رأس، رأس‌های میانی درجهٔ 2 و رأس‌های انتهایی درجهٔ 1 دارند، بنابراین $\Delta(G)=2$.

مقایسهٔ ماکزیمم درجه با دیگر پارامترهای گراف

برای درک بهتر جایگاه Δ(G)، آن را با دو مفهوم دیگر مقایسه می‌کنیم: میانگین درجه و مینیمم درجه⁴. جدول زیر تفاوت‌های اصلی را نشان می‌دهد.

پارامتر	نماد	تعریف	ویژگی مهم
ماکزیمم درجه	Δ(G)	بیشترین درجه در گراف	نشان‌دهندهٔ شلوغ‌ترین رأس
میانگین درجه	\frac{2\|E\|}{\|V\|}	مجموع درجات تقسیم بر تعداد رأس‌ها	معیاری برای تراکم کلی گراف
مینیمم درجه	δ(G)	کمترین درجه در گراف	نشان‌دهندهٔ کم‌تعامل‌ترین رأس

مثال‌های عینی: از شبکهٔ دوستان تا مسابقات ورزشی

فرض کنید در یک کلاس 8 نفره، از هر دانش‌آموز خواسته می‌شود دست دوست خود را بگیرد. اگر گرافی رسم کنیم که رأس‌ها دانش‌آموزان و یال‌ها دست‌دادن‌ها باشند، ماکزیمم درجه مشخص می‌کند چه کسی بیشترین دست‌دادن را داشته است. در یک مسابقهٔ فوتبال دور‌گردشی، هر تیم با چند تیم دیگر بازی می‌کند؛ درجهٔ هر رأس (تیم) تعداد بازی‌های آن تیم است و ماکزیمم درجه نشان‌دهندهٔ تیمی است که بیشترین بازی را انجام داده (مثلاً تیم میزبان که با همه بازی می‌کند).

مثال عددی ساده: گرافی با رأس‌های {A,B,C,D} و یال‌های AB, AC, AD, BC. درجه‌ها: deg(A)=3، deg(B)=2، deg(C)=2، deg(D)=1. بنابراین Δ(G)=3. در یک گراف کامل با n رأس، هر رأس به n-1 رأس دیگر وصل است، پس Δ(G) = n-1.

کاربرد عملی در طراحی شبکه و الگوریتم‌ها

ماکزیمم درجه در طراحی شبکه‌های کامپیوتری اهمیت زیادی دارد. اگر هر رأس یک کامپیوتر باشد و یال‌ها ارتباط فیزیکی، ماکزیمم درجه نشان می‌دهد یک کامپیوتر حداکثر باید چند کابل به آن متصل شود. این عدد بر هزینهٔ کارت‌های شبکه و مدیریت ترافیک تأثیر می‌گذارد. در الگوریتم رنگ‌آمیزی گراف⁵، قضیهٔ معروفی می‌گوید: هر گراف ساده را می‌توان با حداکثر Δ(G)+1 رنگ به‌گونه‌ای رنگ کرد که هیچ دو رأس مجاوری همرنگ نباشند. این قضیه به الگوریتم ترتیبی ساده‌ای منجر می‌شود که در زمان‌بندی امتحانات یا تخصیص فرکانس به کار می‌رود.

مثال: در گراف مسابقات فوتبال با 5 تیم که هر تیم با 2 تیم دیگر بازی می‌کند (یک گراف 2-منتظم)، Δ(G)=2، بنابراین حداکثر 3 رنگ برای رنگ‌آمیزی یال‌ها (زمان‌بندی بازی‌های هم‌زمان) کافی است.

چالش‌های مفهومی

پرسش ۱: آیا ماکزیمم درجه می‌تواند بیشتر از تعداد رأس‌ها منهای یک باشد؟ خیر. در یک گراف ساده بدون یال چندگانه و بدون حلقه، هر رأس حداکثر به |V|-1 رأس دیگر متصل می‌شود. بنابراین Δ(G) \le |V| - 1. در گراف‌های دارای حلقه یا یال چندگانه، این محدودیت برداشته می‌شود.

پرسش ۲: اگر دو رأس مجزا بیشترین درجه را داشته باشند، باز هم ماکزیمم درجه یک عدد است یا چند عدد؟ ماکزیمم درجه یک عدد است: همان مقدار درجهٔ آنها. مثلاً اگر دو رأس هر دو درجهٔ 5 داشته باشند، Δ(G)=5. در تعریف ماکزیمم، به رأس کاری نداریم، فقط به مقدار آن توجه می‌شود.

پرسش ۳: رابطهٔ ماکزیمم درجه با تعداد یال‌ها چیست؟ با استفاده از قضیهٔ دست‌دادن (Handshaking Lemma) داریم $2|E| = \sum_{v} \deg(v) \le |V| \cdot Δ(G)$. بنابراین $|E| \le \frac{|V| \cdot Δ(G)}{2}$. این کران بالا در گراف‌های منتظم که همهٔ رأس‌ها درجهٔ یکسان دارند به تساوی می‌رسد.

جمع‌بندی ماکزیمم درجه Δ(G) یکی از ساده‌ترین و در عین حال بنیادی‌ترین پارامترهای گراف است که حداکثر تعداد همسایگی یک رأس را نشان می‌دهد. این مفهوم در تعیین کران‌های تعداد یال‌ها، تحلیل الگوریتم‌های رنگ‌آمیزی، طراحی شبکه‌های مقاوم و مطالعهٔ گراف‌های منتظم کاربرد دارد. با درک Δ(G)، می‌توان بسیاری از قضایای مهم نظریهٔ گراف مانند قضیهٔ بروکس⁶ را به سادگی فهمید.

پاورقی

¹ قضیهٔ دست‌دادن (Handshaking Lemma): مجموع درجات همهٔ رأس‌های یک گراف برابر دو برابر تعداد یال‌هاست.

² گراف بدون جهت (Undirected Graph): گرافی که در آن یال‌ها جهت ندارند و رابطه بین دو رأس متقارن است.

³ حلقه (Loop): یالی که یک رأس را به خودش متصل می‌کند و معمولاً دو واحد به درجهٔ آن رأس اضافه می‌کند.

⁴ مینیمم درجه (Minimum Degree): کوچکترین درجه در میان رأس‌های گراف که با δ(G) نشان داده می‌شود.

⁵ رنگ‌آمیزی گراف (Graph Coloring): تخصیص برچسب (رنگ) به رأس‌ها به‌طوری که هیچ دو رأس مجاوری رنگ یکسان نداشته باشند.

⁶ قضیهٔ بروکس (Brooks' Theorem): هر گراف همبند ساده که نه کامل باشد و نه دور فرد، با Δ(G) رنگ قابل رنگ‌آمیزی است.

جستجوهای پرتکرار

ماکزیمم درجهٔ گراف Δ(G)