قانون رأسهای فرد در گراف: تعداد رأسهای فرد در هر گراف زوج است
گراف چیست و چرا به درجهٔ رأس نیاز داریم؟
گراف1 در ریاضیات، ساختاری است برای نمایش ارتباط میان اشیاء. یک گراف از دو چیز ساخته میشود: رأسها2 (نقاط یا گرهها) و یالها3 (خطهای اتصال). برای نمونه، فرض کنید در یک مهمانی 5 نفر حضور دارند. هر نفر یک رأس است. اگر دو نفر با هم دست بدهند، بین رأسهای آنها یک یال رسم میکنیم. گراف بهدستآمده، شبکهٔ دستدادنها را نشان میدهد.
یکی از پایهایترین مفاهیم در گراف، درجهٔ رأس4 است. درجهٔ یک رأس، تعداد یالهایی است که به آن متصل هستند. در مثال مهمانی، درجهٔ هر نفر برابر است با تعداد افرادی که با او دست دادهاند. به رأس با درجهٔ فرد، رأس فرد و به رأس با درجهٔ زوج، رأس زوج میگوییم.
حال سؤال این است: آیا میتوان تعداد افرادی که با تعداد فردی از دیگران دست دادهاند، فرد باشد؟ قانون رأسهای فرد پاسخ روشنی میدهد: خیر، این تعداد همیشه زوج است.
قانون دستمصافحه: قلب قضیه
قانونی که پایهٔ اثبات ماست، قانون دستمصافحه5 نام دارد. این قانون میگوید: مجموع درجهٔ همهٔ رأسهای یک گراف بدون جهت، همیشه برابر با دو برابر تعداد یالها است. دلیل آن ساده است: هر یال دقیقاً به دو رأس متصل میشود و در محاسبهٔ مجموع درجهها، هر یال یک واحد به درجهٔ هرکدام از دو سر خود اضافه میکند. بنابراین هر یال دو بار در مجموع کل شمرده میشود.
از آنجایی که $2|E|$ همواره عددی زوج است، پس مجموع درجهٔ همهٔ رأسها همیشه زوج خواهد بود. همین نکتهٔ ساده، کلید اصلی اثبات ما است.
اثبات گامبهگام تعداد زوج رأسهای فرد
حال نشان میدهیم که چرا تعداد رأسهای فرد ناگزیر زوج است. این اثبات تنها با استفاده از جمع و تقسیمبندی درجهها انجام میشود.
گام اول: مجموع درجهٔ همهٔ رأسها را به دو بخش تقسیم میکنیم: مجموع درجهٔ رأسهای زوج بهعلاوهٔ مجموع درجهٔ رأسهای فرد.
$\sum_{v \in V} \deg(v) = \sum_{\text{رأسهای زوج}} \deg(v) + \sum_{\text{رأسهای فرد}} \deg(v)$.گام دوم: میدانیم مجموع کل (طرف چپ) یک عدد زوج است. همچنین مجموع درجهٔ رأسهای زوج، حاصلجمع چند عدد زوج است که باز هم زوج خواهد بود. بنابراین:
$\underbrace{\sum_{\text{رأسهای زوج}} \deg(v)}_{\text{زوج}} + \underbrace{\sum_{\text{رأسهای فرد}} \deg(v)}_{\text{?}} = \text{زوج}$.گام سوم: از آنجا که «زوج + مقدار = زوج»، نتیجه میگیریم که مقدار $\sum_{\text{رأسهای فرد}} \deg(v)$ نیز باید یک عدد زوج باشد.
گام چهارم: مجموع درجهٔ رأسهای فرد، حاصلجمع چند عدد فرد است. چه زمانی حاصلجمع چند عدد فرد، زوج میشود؟ تنها زمانی که تعداد این اعداد فرد، زوج باشد (چون مجموع هر دو عدد فرد یک عدد زوج میسازد). بنابراین تعداد رأسهای فرد باید زوج باشد. اثبات کامل شد.
نکته کلیدی: هیچ الزامی وجود ندارد که تعداد رأسهای زوج حتماً زوج یا فرد باشد. تنها قانون مربوط به تعداد رأسهای فرد است که همواره زوج است.
جدول مقایسهٔ رأس فرد در گرافهای مختلف
| نوع گراف | تعداد رأسها | تعداد یالها | لیست درجهٔ رأسها | تعداد رأسهای فرد |
|---|---|---|---|---|
| گراف خطی با 4 رأس | 4 | 3 | 1, 2, 2, 1 | 2 (زوج) |
| مثلث (گراف کامل K3) | 3 | 3 | 2, 2, 2 | 0 (زوج) |
| ستارهٔ 5 پرتو | 5 | 4 | 1, 1, 1, 1, 4 | 4 (زوج) |
| مربع (چهارضلعی) | 4 | 4 | 2, 2, 2, 2 | 0 (زوج) |
کاربرد واقعی: شبکهٔ ارتباطات و مسیریابی
قانون رأسهای فرد در طراحی شبکههای کامپیوتری، مدارهای الکتریکی و حتی برنامهریزی مسیر پستچی (مسئلهٔ مسیر اویلری) کاربرد دارد. برای نمونه، اگر در یک شبکه بخواهیم مسیری پیدا کنیم که از هر پل یا خیابان دقیقاً یک بار عبور کند (مسیر اویلر)، طبق قضیهٔ اویلر، گراف باید حداکثر 0 یا 2 رأس فرد داشته باشد. دانستن اینکه تعداد رأسهای فرد زوج است، به مهندسان کمک میکند تا بدون آزمون و خطا بفهمند که چنین مسیری وجود دارد یا خیر.
مثال دیگر: در یک کنفرانس با 10 شرکتکننده، اگر بخواهیم تعداد افرادی که با تعداد فردی از دیگران تبادل نظر کردهاند را بشماریم، میتوانیم مطمئن باشیم این تعداد زوج است. اگر خلاف آن را مشاهده کردیم، یعنی اشتباهی در شمارش رخ داده است.
چالشهای مفهومی
۱. آیا ممکن است گرافی داشته باشیم که دقیقاً 1 رأس فرد داشته باشد؟
خیر. طبق قانون اثبات شده، تعداد رأسهای فرد حتماً زوج است. پس هیچ گرافی نمیتواند دقیقاً 1، 3 یا 5 رأس فرد داشته باشد. چنین گرافی در دنیای ریاضیات وجود خارجی ندارد.
۲. آیا گراف بدون یال (گراف تهی) از این قانون پیروی میکند؟
بله. در گراف تهی با هر تعداد رأس، درجهٔ همهٔ رأسها صفر است که عددی زوج محسوب میشود. بنابراین تعداد رأسهای فرد برابر صفر است که عددی زوج میباشد. قانون در این حالت مرزی نیز برقرار است.
۳. اگر در یک گراف جهتدار به جای گراف بدون جهت نگاه کنیم، آیا این قانون همچنان برقرار است؟
خیر. قانون رأسهای فرد و قضیهٔ دستمصافحه برای گرافهای جهتدار به شکل دیگری بیان میشود. در گراف جهتدار، مجموع درجهٔ ورودی همهٔ رأسها برابر مجموع درجهٔ خروجی و برابر تعداد یالها است، اما تعداد رأسهای با مجموع درجه (ورودی+خروجی) فرد میتواند فرد یا زوج باشد. قانون زوج بودن رأسهای فرد مختص گرافهای بدون جهت است.
جمعبندی
پاورقی
1 گراف (Graph): ساختاری متشکل از مجموعهٔ رأسها و مجموعهٔ یالها که رابطهٔ دودویی میان رأسها را نمایش میدهد.
2 رأس (Vertex): یک نقطه یا گره در گراف که نمایانگر یک شیء یا موجودیت است.
3 یال (Edge): ارتباط یا پیوند میان دو رأس در گراف که ممکن است جهتدار یا بدون جهت باشد.
4 درجهٔ رأس (Degree of a Vertex): تعداد یالهای متصل به یک رأس در گراف بدون جهت.
5 قانون دستمصافحه (Handshaking Lemma): قضیهای که میگوید مجموع درجهٔ همهٔ رأسهای هر گراف بدون جهت برابر با دو برابر تعداد یالها است.
