مینیمم درجهٔ گراف: کوچکترین درجهٔ رأسها
تعریف پایه و نمادگذاری مینیمم درجه
در نظریهٔ گراف، به هر رأس (نقطه) تعدادی یال (خط) متصل میشود که به این تعداد، «درجهٔ رأس» میگویند. اگر گراف ساده4 و بدون جهت5 داشته باشیم، درجهٔ هر رأس برابر است با شمار یالهایی که از آن خارج یا به آن وارد میشوند. حال اگر بخواهیم کوچکترین درجه را در میان همهٔ رأسهای گراف پیدا کنیم، به آن «مینیمم درجه» میگوییم و با نماد $ \delta(G) $ نشان میدهیم.
به زبان ساده: اگر از هر رأس بپرسیم «چند یال داری؟» و کمترین پاسخی که میشنویم را یادداشت کنیم، همان مینیمم درجه است.
برای یک گراف $ G $ با مجموعهٔ رأسهای $ V(G) $ و مجموعهٔ یالهای $ E(G) $، اگر درجهٔ رأس $ v $ را با $ \deg(v) $ نشان دهیم، آنگاه:
برای نمونه، یک گراف با $ 5 $ رأس در نظر بگیرید که درجهٔ رأسها به ترتیب $ 2, 3, 1, 4, 2 $ باشد. در اینجا مینیمم درجه برابر $ 1 $ است. رأس با درجهٔ $ 1 $ را «رأس برگ» نیز مینامند.
ارتباط با قضیهٔ دست دادن و جمع درجات
یکی از قضیههای بنیادین در نظریهٔ گراف، «قضیهٔ دست دادن» است که بیان میکند مجموع درجات همهٔ رأسهای یک گراف، برابر است با دو برابر تعداد یالها. به عبارت ریاضی:
با استفاده از مینیمم درجه میتوان یک کران پایین برای مجموع درجات به دست آورد. اگر گراف $ n $ رأس داشته باشد، آنگاه:
و در نتیجه $ 2|E(G)| \ge n \cdot \delta(G) $ یا به عبارتی $ |E(G)| \ge \frac{n \cdot \delta(G)}{2} $. این رابطه نشان میدهد که هرچه مینیمم درجه بزرگتر باشد، گراف ناچار به داشتن یالهای بیشتری است.
مثال عملی: فرض کنید در یک شبکهٔ دوستی با $ 10 $ نفر، هر فرد حداقل با $ 3 $ نفر دیگر دوست است (یعنی $ \delta(G)=3 $). طبق رابطهٔ بالا، تعداد دستدادنها (یالها) حداقل $ \frac{10 \times 3}{2} = 15 $ خواهد بود. این یک تخمین سریع از تراکم ارتباطات ارائه میدهد.
مقایسهٔ مینیمم درجه با ماکسیمم و میانگین درجه
برای درک بهتر جایگاه مینیمم درجه، آن را با دو پارامتر دیگر مقایسه میکنیم: ماکسیمم درجه $ \Delta(G) $ و میانگین درجه $ \bar{d}(G) $. جدول زیر تفاوتهای کلیدی را نشان میدهد.
| پارامتر | نماد | معنی | کاربرد معمول |
|---|---|---|---|
| مینیمم درجه | $ \delta(G) $ | کمترین تعداد یال متصل به یک رأس | اطمینان از وجود رأسهای کماتصال |
| ماکسیمم درجه | $ \Delta(G) $ | بیشترین تعداد یال متصل به یک رأس | شناسایی رأسهای پرطرفدار یا مرکزی |
| میانگین درجه | $ \bar{d}(G) $ | مجموع درجات تقسیم بر تعداد رأسها | برآورد چگالی کلی گراف |
رابطهٔ مهم میان این سه پارامتر به صورت زیر است:
همیشه مینیمم درجه از میانگین درجه کوچکتر یا مساوی است. این نامساوی به ما کمک میکند تا با دانستن مینیمم درجه، به کران پایینی برای میانگین درجه پی ببریم.
کاربرد عملی: تحلیل شبکههای اجتماعی و مسیرهای همیلتونی
در شبکههای اجتماعی، مینیمم درجه نشاندهندهٔ کمترین تعداد ارتباط یک فرد است. اگر $ \delta(G) $ عدد بزرگی باشد، یعنی شبکه «چگال» است و هیچ فردی در انزوا قرار ندارد. به عنوان مثال، در یک کلاس درس، اگر مینیمم درجه بین دانشآموزان برابر $ 2 $ باشد، هر دانشآموز حداقل با دو نفر دیگر آشناست و شبکه از گسستگی دور میشود.
یکی از قضیههای معروف در نظریهٔ گراف، قضیهٔ دیراک6 است: اگر در یک گراف ساده با $ n \ge 3 $ رأس، مینیمم درجه از $ \frac{n}{2} $ بیشتر باشد، آنگاه گراف دارای یک دور همیلتونی7 (مسیری که از همهٔ رأسها دقیقاً یک بار عبور کرده و به چرخهٔ همیلتونی بازگردد) خواهد بود. این قضیه نشان میدهد که مینیمم درجه بالا وجود مسیرهای فراگیر را تضمین میکند.
$ \delta(G) \ge \frac{n}{2} \quad \Rightarrow \quad G \text{ دارای دور همیلتونی است} $
مثال عددی: گرافی با $ n = 6 $ رأس در نظر بگیرید. اگر هر رأس حداقل درجهٔ $ 3 $ داشته باشد ($ \delta(G)=3 $)، چون $ 3 \ge \frac{6}{2} $، طبق قضیهٔ دیراک گراف دارای یک دور همیلتونی است. یعنی میتوان ترتیبی از رأسها پیدا کرد که دنبالهای بسته از یالها را تشکیل دهد و همهٔ رأسها را یک بار ملاقات کند.
چالشهای مفهومی
چالش ۱: آیا ممکن است مینیمم درجهٔ یک گراف صفر باشد؟ این وضعیت چه معنایی دارد؟
بله، اگر حداقل یک رأس در گراف وجود داشته باشد که به هیچ رأس دیگری متصل نباشد (رأس تنها یا ایزوله)، آنگاه $ \delta(G) = 0 $. این یعنی گراف ناهمبند است و آن رأس هیچ نقشی در ارتباطات ندارد.
چالش ۲: اگر در یک گراف کامل8 با $ n $ رأس، مینیمم درجه چقدر است؟
در گراف کامل، هر رأس به همهٔ سایر رأسها متصل است، بنابراین درجهٔ هر رأس برابر $ n-1 $ است. از آنجایی که همهٔ درجات یکسانند، مینیمم درجه نیز برابر $ n-1 $ خواهد بود. پس $ \delta(K_n) = n-1 $.
چالش ۳: آیا گرافی با مینیمم درجهٔ بالا لزوماً همبند است؟
نه لزوماً، اما اگر $ \delta(G) \ge 1 $ باشد، گراف میتواند همبند یا ناهمبند باشد. با این حال اگر $ \delta(G) \ge \frac{n}{2} $ باشد، گراف نه تنها همبند است، بلکه بنا بر قضیهٔ دیراک دور همیلتونی نیز دارد.
جمعبندی
پاورقی
2 قضیهٔ دست دادن (Handshaking Lemma): قضیهای که میگوید مجموع درجات رأسها دو برابر تعداد یالهاست.
3 مسیر همیلتونی (Hamiltonian Path): مسیری در گراف که از هر رأس دقیقاً یک بار عبور میکند.
4 گراف ساده (Simple Graph): گرافی بدون یال موازی و بدون حلقه (یالی که یک رأس را به خودش متصل میکند).
5 گراف بدون جهت (Undirected Graph): گرافی که یالها جهت ندارند و رابطه بین دو رأس متقارن است.
6 قضیهٔ دیراک (Dirac's Theorem): قضیهای که شرط کافی برای وجود دور همیلتونی را بر اساس مینیمم درجه بیان میکند.
7 دور همیلتونی (Hamiltonian Cycle): مسیر همیلتونی بسته که به رأس شروع بازگردد.
8 گراف کامل (Complete Graph): گرافی که هر دو رأس متمایز آن با یک یال به هم متصل شدهاند و با $ K_n $ نشان داده میشود.