مجموع درجات رأس‌های گراف: جمع درجهٔ همهٔ رأس‌های گراف

مجموع درجات رأس‌های گراف: قانون دست دادن و کاربردهای آن

درجهٔ یک رأس چیست و چگونه محاسبه می‌شود؟

در نظریهٔ گراف، یک گراف از دو چیز ساخته می‌شود: رأس‌ها (که گاهی گره² هم نامیده می‌شوند) و یال‌ها³ که آن‌ها را به هم متصل می‌کنند. «درجهٔ یک رأس» تعداد یال‌هایی است که به آن رأس متصل می‌شوند. به عبارت ساده‌تر، اگر هر یال را یک رابطه در نظر بگیریم، درجه نشان می‌دهد که آن رأس با چند رأس دیگر رابطه مستقیم دارد.

مثال ۱ فرض کنید در یک مهمانی 5 نفر حضور دارند. هر دست دادن بین دو نفر، یک یال در گراف است. اگر شخص «علی» با 3 نفر دیگر دست بدهد، درجهٔ رأس مربوط به علی برابر 3 خواهد بود. رأس‌هایی که هیچ یالی به آن‌ها متصل نیست، درجهٔ صفر دارند و «رأس تنها»⁴ نامیده می‌شوند.

قانون دست دادن: قضیهٔ بنیادی مجموع درجات

یکی از مشهورترین قضایای نظریهٔ گراف، «قانون دست دادن» است. این قانون بیان می‌کند که در هر گراف بدون جهت، مجموع درجات همهٔ رأس‌ها همواره برابر با دو برابر تعداد یال‌ها است. دلیل آن ساده است: هر یال دقیقاً به دو رأس متصل می‌شود، بنابراین هر یال در مجموع درجات، به اندازهٔ 2 واحد (یک واحد برای هر کدام از دو رأس خود) نقش دارد.

نکتهٔ مهم: طبق این قانون، مجموع درجات همیشه یک عدد زوج است. از این رو، تعداد رأس‌هایی که درجهٔ فرد دارند در هر گراف، همواره زوج خواهد بود. این یک نتیجهٔ کلیدی و ساده برای اثبات بسیاری از قضایای دیگر است.

محاسبهٔ مجموع درجات در گراف جهت‌دار

در گراف جهت‌دار، هر یال یک جهت (پیکان) دارد. در اینجا برای هر رأس دو نوع درجه تعریف می‌شود: درجهٔ ورودی⁷ (تعداد یال‌هایی که به آن رأس وارد می‌شوند) و درجهٔ خروجی⁸ (تعداد یال‌هایی که از آن رأس خارج می‌شوند). جمع تمام درجه‌های ورودی برابر با جمع تمام درجه‌های خروجی و همچنین برابر با تعداد کل یال‌های جهت‌دار است.

به عنوان مثال، در یک شبکهٔ اجتماعی دنبال‌کننده (مثل اینستاگرام)، اگر جهت یال را از «دنبال‌کننده» به «دنبال‌شونده» در نظر بگیریم، درجهٔ خروجی یک کاربر نشان می‌دهد چند نفر را دنبال می‌کند و درجهٔ ورودی او نشان می‌دهد چند دنبال‌کننده دارد. برابری مجموع درجه‌های ورودی و خروجی در کل شبکه، یک واقعیت بدیهی اما جالب است: تعداد کل دنبال‌کردن‌ها (یال‌ها) از هر دو دیدگاه یکسان محاسبه می‌شود.

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

فرض کنید نقشهٔ متروی یک شهر به صورت گراف نمایش داده شده است. ایستگاه‌ها رأس‌ها و خطوط بین آن‌ها یال‌ها هستند. مجموع درجات رأس‌ها می‌تواند در محاسبهٔ «مرکزیت درجه»⁹ هر ایستگاه به کار رود. ایستگاهی با درجهٔ بالاتر، اتصال بیشتری به خطوط دیگر دارد و احتمالاً یک گرهٔ کلیدی در شبکه است. همچنین قانون دست دادن به مهندسان کمک می‌کند تا بدون شمردن تک‌تک مسیرها، سریعاً تعداد کل تونل‌ها یا خطوط را بررسی کنند. مثلاً اگر مجموع درجات همهٔ ایستگاه‌ها 42 باشد، بلافاصله می‌دانیم که تعداد یال‌ها (قطعات مسیر بین ایستگاه‌ها) برابر 21 است.

مثال ۲ در یک کارگاه تولیدی، ماشین‌ها به صورت گراف به هم متصل شده‌اند. هر یال نشان‌دهندهٔ یک لولهٔ انتقال مواد است. اگر بدانیم مجموع درجات رأس‌ها 30 است، تعداد لوله‌ها (یال‌ها) برابر 15 خواهد بود. این محاسبه سریع، به مهندسان در برآورد هزینه و زمان تعمیرات کمک می‌کند.

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

پاورقی

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

² گره (Node): معادل دیگر رأس در نظریهٔ گراف و شبکه.

³ یال (Edge): ارتباط یا پیوند بین دو رأس در گراف.

⁴ رأس تنها (Isolated Vertex): رأسی با درجهٔ صفر که به هیچ یالی متصل نیست.

⁵ یال‌های Incident: یال‌هایی که به یک رأس متصل هستند.

⁶ حلقه (Loop): یالی که یک رأس را به خودش وصل می‌کند.

⁷ درجهٔ ورودی (Indegree): تعداد یال‌هایی که به یک رأس وارد می‌شوند در گراف جهت‌دار.

⁸ درجهٔ خروجی (Outdegree): تعداد یال‌هایی که از یک رأس خارج می‌شوند در گراف جهت‌دار.

⁹ مرکزیت درجه (Degree Centrality): معیاری برای سنجش اهمیت یک رأس بر اساس تعداد همسایگان آن.

¹⁰ یال چندگانه (Multiedge): وجود بیش از یک یال بین دو رأس مشخص.

¹¹ گراف اویلری (Eulerian Graph): گرافی که دارای مسیری بسته باشد که از هر یال دقیقاً یک بار عبور کند.

¹² گراف همیلتونی (Hamiltonian Graph): گرافی که دارای دوری باشد که از هر رأس دقیقاً یک بار عبور کند.