رأس زوج در گراف؛ مفاهیم پایه و کاربردها
درجهٔ رأس و مفهوم رأس زوج
در نظریهٔ گراف2، یک گراف از مجموعهٔ رأسها3 و یالها4 تشکیل شده است. اگر دو رأس توسط یک یال به هم متصل باشند، میگوییم آن دو رأس مجاور هستند. هر رأس میتواند با تعدادی رأس دیگر مجاور باشد. تعداد یالهایی که به یک رأس متصل میشوند، درجهٔ آن رأس نامیده میشود.
رأس زوج به رأسی گفته میشود که درجهٔ آن یک عدد زوج باشد. برای نمونه اگر یک رأس دقیقاً به 2، 4، 6 یا به طور کلی $2k$ (که $k$ یک عدد طبیعی است) یال متصل باشد، آن رأس زوج نامیده میشود. در مقابل، رأس فرد رأسی با درجهٔ فرد است (مانند $1,3,5,\dots$).
- رأس A به 3 یال (AB, AC, AD) متصل است ← درجهٔ 3 (فرد)
- رأس B به 3 یال (AB, BC, BD) ← درجهٔ 3 (فرد)
- رأس C به 2 یال (AC, BC, CE توجه: CE هم اضافه است) در اصل C به AC, BC, CE یعنی 3 یال (بازبینی کنید) – بهتر است مثالی سادهتر بزنیم. مثال اصلاحشده: گراف با رأسهای X, Y, Z, W و یالهای XY, XZ, YZ, ZW. درجهٔ X برابر 2 (زوج)، درجهٔ Y برابر 2 (زوج)، درجهٔ Z برابر 3 (فرد)، درجهٔ W برابر 1 (فرد). در اینجا رأسهای X و Y رأسهای زوج هستند.
قضیهٔ دستمصافحه و نقش رأسهای زوج
یکی از قضایای بنیادین در نظریهٔ گراف، قضیهٔ دستمصافحه است. این قضیه میگوید: مجموع درجات همهٔ رأسهای یک گراف، برابر با دو برابر تعداد یالها است. به زبان ریاضی:
$\sum_{v \in V} \deg(v) = 2|E|$که $V$ مجموعهٔ رأسها و $|E|$ تعداد یالها است. از آنجا که سمت راست همواره یک عدد زوج است، نتیجه میگیریم: تعداد رأسهای با درجهٔ فرد در هر گراف، همیشه زوج است. به عبارت دیگر، تعداد رأسهای فرد نمیتواند فرد باشد. این نتیجهٔ مهم به طور غیرمستقیم بر اهمیت رأسهای زوج تأکید میکند زیرا رأسهای زوج میتوانند هر تعدادی داشته باشند (حتی صفر) اما رأسهای فرد حتماً به تعداد زوج ظاهر میشوند.
مقایسهٔ رأس زوج و رأس فرد در یک نگاه
| ویژگی | رأس زوج | رأس فرد |
|---|---|---|
| تعریف درجه | $\deg(v) \equiv 0 \pmod{2}$ | $\deg(v) \equiv 1 \pmod{2}$ |
| تعداد در گراف دلخواه | هر عدد صحیح نامنفی (از 0 تا n) | همیشه زوج (صفر، دو، چهار، ...) |
| شرط وجود مدار اویلری5 | همهٔ رأسها زوج باشند | حداکثر 2 رأس فرد مجاز است (مسیر اویلری) |
| مثال ساده | مثلث (هر رأس درجه 2) | گراف ستارهٔ K_{1,3} (مرکز درجه 3 و سه برگ درجه 1) |
کاربرد عملی: نقشهٔ شهر و تور پستچی
یکی از مسائل کلاسیک که به رأسهای زوج مرتبط است، مسیر پستچی چینی است. فرض کنید یک پستچی میخواهد از تمام خیابانهای یک منطقه (یالها) عبور کند و به نقطهٔ شروع بازگردد. این مسئله زمانی امکانپذیر است که درجهٔ همهٔ تقاطعها (رأسها) زوج باشد. در غیر این صورت، پستچی ناچار است برخی یالها را دوباره طی کند. با افزودن یالهای مصنوعی (تکراری) میتوان درجهٔ رأسهای فرد را به زوج تبدیل کرد.
مثال عینی: فرض کنید نقشهٔ یک پارک شامل 4 تقاطع است. تقاطع A به B و C راه دارد، تقاطع B به A و D، تقاطع C به A و D و تقاطع D به B و C. در این گراف هر رأس درجهٔ 2 دارد (همه زوج) بنابراین پستچی میتواند مسیری بیابد که از هر خیابان دقیقاً یک بار عبور کند و به نقطهٔ اول برگردد (مدار اویلری).
چالشهای مفهومی
پاسخ: خیر. بر اساس قضیهٔ دستمصافحه، تعداد رأسهای فرد در هر گراف زوج است. بنابراین 3 رأس فرد غیرممکن است. میتواند 0، 2، 4 و ... باشد.
پاسخ: بله، زیرا صفر یک عدد زوج است. چنین رأسی هیچ یالی به سایر رأسها ندارد و به آن رأس منزوی میگویند. در بسیاری از قضایا، رأس منزوی نیز مانند سایر رأسهای زوج رفتار میکند.
پاسخ: برای وجود مدار اویلری، علاوه بر زوج بودن همهٔ رأسها، گراف باید همبند6 نیز باشد (به جز رأسهای تنها). اگر گرافی همبند باشد و همهٔ رأسها درجهٔ زوج داشته باشند، آنگاه دارای مدار اویلری است.
جمعبندی
پاورقی
2 نظریهٔ گراف (Graph Theory): شاخهای از ریاضیات که به مطالعهٔ گرافها و ویژگیهای آنها میپردازد.
3 رأس (Vertex): یکی از نقاط یا گرههای تشکیلدهندهٔ گراف که معمولاً با یک دایره نشان داده میشود.
4 یال (Edge): پلی بین دو رأس که نشاندهندهٔ ارتباط میان آنها است.
5 مدار اویلری (Eulerian Circuit): دوری در گراف که از هر یال دقیقاً یک بار عبور کرده و به نقطهٔ شروع بازگردد.
6 گراف همبند (Connected Graph): گرافی که بین هر دو رأس آن حداقل یک مسیر وجود داشته باشد.