درجهٔ رأس در گراف: مفهوم پایهای و کاربردها
تعریف درجهٔ رأس و انواع آن در گراف
در نظریه گراف1، به هر نقطه یا گره، «رأس»2 و به هر خط ارتباطی بین دو رأس، «یال»3 میگویند. درجهٔ یک رأس برابر است با تعداد یالهایی که آن رأس را به سایر رأسها متصل میکند. اگر گراف بدون جهت (غیرجهتدار) باشد، درجهٔ هر رأس به سادگی با شمردن یالهای متصل به آن محاسبه میشود.
به عنوان مثال، فرض کنید یک گراف ساده با 5 رأس داریم که به شکل یک ستاره طراحی شده است. رأس مرکزی به هر 4 رأس دیگر متصل است، بنابراین درجهٔ آن برابر 4 خواهد بود. رأسهای محیطی تنها به رأس مرکزی متصل هستند و درجهٔ آنها 1 است. این مثال ساده نشان میدهد که درجهٔ رأس میتواند از 0 (رأس تنها) تا n-1 (گراف کامل) تغییر کند.
در گراف جهتدار، مفهوم درجه به دو بخش تقسیم میشود: درجهٔ ورودی و درجهٔ خروجی. درجهٔ ورودی تعداد یالهایی است که به رأس وارد میشوند و درجهٔ خروجی تعداد یالهایی است که از رأس خارج میشوند. برای نمونه، در یک شبکهٔ اجتماعی که دنبالکنندگان را نشان میدهد، درجهٔ ورودی هر کاربر تعداد دنبالکنندگان او و درجهٔ خروجی تعداد افرادی است که او دنبال میکند.
جدول مقایسهٔ درجه در گرافهای مختلف
| نوع گراف | معنی درجهٔ رأس | حدود مقادیر ممکن | مثال عددی |
|---|---|---|---|
| گراف ساده بدون جهت | تعداد یالهای متصل به رأس | 0 تا n-1 | رأس مرکزی در گراف ستاره: 4 |
| گراف جهتدار | (ورودی، خروجی) مجموعاً | 0 تا 2(n-1) | رأس با 2 ورودی و 3 خروجی: مجموع 5 |
| گراف با حلقه (Loop) | حلقه معمولاً 2 واحد به درجه اضافه میکند | وابسته به تعداد حلقهها | رأس با یک حلقه: درجهٔ 2 |
کاربرد عملی: تحلیل شبکهٔ دوستان در یک کلاس
فرض کنید در یک کلاس 30 نفره، هر دانشآموز با تعدادی از دیگران دوست است. اگر این رابطه را به صورت یک گراف بدون جهت رسم کنیم، هر دانشآموز یک رأس و هر رابطهٔ دوستی یک یال است. درجهٔ هر رأس نشان میدهد که آن دانشآموز چند دوست در کلاس دارد. با محاسبهٔ درجات میتوانیم:
- محبوبترین فرد (بیشترین درجه) را پیدا کنیم.
- افرادی که هیچ دوستی ندارند (درجهٔ صفر) را شناسایی کنیم.
- با استفاده از قضیه دست دادن، تعداد کل دوستیها را بدون نیاز به شمردن مستقیم به دست آوریم.
برای مثال، اگر مجموع درجات همهٔ دانشآموزان برابر 84 باشد، آنگاه تعداد یالها (دوستیها) برابر 42 خواهد بود، زیرا هر یال در مجموع درجات دو بار شمارش میشود. این روش محاسبه بسیار سریعتر از فهرست کردن تکتک دوستیهاست.
$ \sum_{v \in V} \deg(v) = 2|E| $
این قضیه به این دلیل برقرار است که هر یال دقیقاً به دو رأس متصل است و بنابراین در محاسبهٔ مجموع درجات، دو بار ظاهر میشود.
چالشهای مفهومی در درک درجهٔ رأس
۱) آیا یک رأس میتواند به خودش متصل شود؟ در این حالت درجه چگونه محاسبه میشود؟
بله، به چنین یالی «حلقه» (Loop) میگویند. در اغلب تعریفهای استاندارد، یک حلقه به اندازهٔ 2 واحد به درجهٔ آن رأس اضافه میکند، زیرا هر حلقه دو بار (یک بار به عنوان شروع و یک بار به عنوان پایان) در محاسبهٔ درجه نقش دارد تا قضیه دست دادن همچنان برقرار بماند.
۲) اگر گراف جهتدار باشد، چگونه میتوان درجهٔ کل یک رأس را گزارش کرد؟
در گراف جهتدار، معمولاً درجهٔ کل را مجموع درجهٔ ورودی و درجهٔ خروجی تعریف میکنیم: $ \deg(v) = \deg^-(v) + \deg^+(v) $. همچنین رابطهٔ مشابه قضیه دست دادن به صورت $ \sum_{v \in V} \deg^-(v) = \sum_{v \in V} \deg^+(v) = |E| $ برقرار است.
۳) چه ارتباطی بین درجهٔ رأس و وجود مسیر اویلر در گراف وجود دارد؟
در گراف بدون جهت، مسیر اویلر (مسیری که از هر یال دقیقاً یک بار عبور کند) وجود دارد اگر و تنها اگر حداکثر دو رأس با درجهٔ فرد داشته باشیم. همچنین مدار اویلر (مسیر بسته) زمانی وجود دارد که درجهٔ همهٔ رأسها زوج باشد. این قضیه که به قضیه اویلر معروف است، یکی از کاربردهای مهم مفهوم درجهٔ رأس در نظریه گراف است.
جمعبندی
پاورقی
1 نظریه گراف (Graph Theory): شاخهای از ریاضیات گسسته که به مطالعهٔ روابط بین اشیاء با استفاده از ساختارهای متشکل از رأس و یال میپردازد.
2 رأس (Vertex): یک نقطه یا گره در گراف که نشاندهندهٔ یک شیء یا موجودیت است.
3 یال (Edge): ارتباط یا پیوند بین دو رأس در گراف که میتواند جهتدار یا بدون جهت باشد.
4 گراف ساده (Simple Graph): گرافی بدون حلقه و بدون یال چندگانه بین یک زوج رأس مشخص.
5 قضیه دست دادن (Handshaking Lemma): قضیهای که نشان میدهد مجموع درجات رأسهای یک گراف بدون جهت برابر دو برابر تعداد یالهاست.
