رأس فرد در گراف: رأسی با درجهٔ فرد در گراف
۱. درجه رأس و مفهوم رأس فرد
در نظریه گراف1، یک گراف $G$ از مجموعه رأسها $V$ و مجموعه یالها $E$ تشکیل میشود. درجه یک رأس مانند $v$ که آن را با $\deg(v)$ نمایش میدهند، برابر است با تعداد یالهایی که به آن رأس متصل هستند. اگر $\deg(v)$ عددی فرد باشد، آن رأس را رأس فرد مینامیم. برای نمونه، در یک گراف ساده، راسی که به سه رأس دیگر متصل است، یک رأس فرد محسوب میشود. در مقابل، رأس زوج به رأسی گفته میشود که درجه آن زوج باشد.
۲. قضیه دست دادن و نقش رأسهای فرد
یکی از قضایای بنیادین در نظریه گراف، قضیه دست دادن است که میگوید: مجموع درجات همه رأسهای یک گراف برابر است با دو برابر تعداد یالها. به زبان ریاضی:
از آنجا که طرف راست معادله همواره عددی زوج است، مجموع درجات همه رأسها نیز باید زوج باشد. این نتیجه مهمی در مورد رأسهای فرد به دست میدهد: تعداد رأسهای فرد در هر گراف همواره زوج است. یعنی نمیتوانیم گرافی داشته باشیم که دقیقاً $1$ رأس فرد یا $3$ رأس فرد داشته باشد؛ بلکه تعداد آنها میتواند $0, 2, 4, 6, \dots$ باشد.
| ویژگی | رأس فرد | رأس زوج |
|---|---|---|
| درجه | $1,3,5,7,\dots$ | $0,2,4,6,\dots$ |
| تعداد در گراف معمولی | همیشه زوج | هر تعداد دلخواه |
| نقش در مسیر اویلری2 | نقطه شروع یا پایان مسیر در مسیر نیمهاویلری | رأسهای میانی در مسیر اویلری |
۳. روش شناسایی رأسهای فرد در گراف
برای شناسایی رأسهای فرد در یک گراف، کافی است درجه هر رأس را محاسبه کنیم و سپس ببینیم کدام درجهها فرد هستند. در گرافهای ساده بدون حلقه3، درجه هر رأس برابر با تعداد همسایگان آن است. مراحل گامبهگام:
- گام اول: فهرست همه رأسهای گراف را بنویسید.
- گام دوم: برای هر رأس، تعداد یالهای متصل به آن را بشمارید (به هر یال یک بار از دید هر رأس نگاه کنید).
- گام سوم: اگر عدد حاصل بر $2$ بخشپذیر نبود، آن رأس را در دسته رأسهای فرد قرار دهید.
- گام چهارم: تعداد رأسهای فرد را بشمارید تا از زوج بودن آن اطمینان حاصل کنید (این یک روش خطایابی است).
به عنوان مثال، گرافی با $4$ رأس به نامهای $A, B, C, D$ و یالهای $AB, BC, CD, DA$ (یک چهارضلعی) در نظر بگیرید. در اینجا هر رأس درجه $2$ دارد (زوج) بنابراین هیچ رأس فردی وجود ندارد. اگر یال $AC$ را اضافه کنیم، درجات رأسهای $A$ و $C$ به $3$ تبدیل میشوند (فرد) و رأسهای $B$ و $D$ درجه $2$ باقی میمانند، بنابراین $2$ رأس فرد داریم که عددی زوج است.
۴. کاربرد عملی: مسیریابی و شبکههای مخابراتی
شناسایی رأسهای فرد در مسائل مسیریابی مانند مسأله پستبان (مسیر اویلری) کاربرد مستقیم دارد. در یک گراف، مسیر اویلری (مسیری که از هر یال دقیقاً یک بار بگذرد) وجود دارد اگر و تنها اگر تعداد رأسهای فرد برابر با $0$ یا $2$ باشد. اگر تعداد رأسهای فرد $0$ باشد، مسیر بسته (دور اویلری) و اگر $2$ باشد، مسیر باز (آغاز و پایان در دو رأس فرد) داریم.
در عمل، شهرداری یک شهر که میخواهد ماشینهای حمل زباله را طوری هدایت کند که هر خیابان دقیقاً یک بار پیموده شود، نخست نقشه شهر را به صورت گراف درمیآورد و رأسهای فرد را میشمارد. اگر بیش از $2$ رأس فرد وجود داشته باشد، باید با افزودن یالهای مجازی (تکرار بعضی خیابانها) تعداد آنها را به $0$ یا $2$ کاهش داد تا مسیر بهینه به دست آید.
۵. چالشهای مفهومی
۱) آیا گرافی وجود دارد که دقیقاً یک رأس فرد داشته باشد؟
خیر. بر اساس قضیه دست دادن، مجموع درجات همه رأسها زوج است. اگر تنها یک رأس فرد وجود داشته باشد، مجموع درجات فرد میشود (چون مجموع درجات دیگر رأسها زوج است و یک عدد فرد با زوج جمع شود، فرد میشود). این با زوج بودن مجموع کل در تناقض است. بنابراین چنین گرافی غیرممکن است.
۲) آیا در گراف کامل $K_n$ با $n$ رأس، تعداد رأسهای فرد چقدر است؟
در گراف کامل $K_n$، درجه هر رأس برابر $n-1$ است. اگر $n-1$ فرد باشد (یعنی $n$ زوج باشد)، همه $n$ رأس فرد خواهند بود. اگر $n-1$ زوج باشد (یعنی $n$ فرد باشد)، هیچ رأس فردی وجود ندارد. در هر دو حالت، تعداد رأسهای فرد زوج است (عدد $n$ وقتی زوج باشد یا عدد $0$).
۳) چگونه میتوان با افزودن یک یال جدید، تعداد رأسهای فرد را تغییر داد؟
افزودن یک یال بین دو رأس، درجه هر دو رأس را یک واحد افزایش میدهد. بنابراین هر یک از آن دو رأس از زوج به فرد یا از فرد به زوج تغییر وضعیت میدهند. در نتیجه تعداد رأسهای فرد یا $0$ تغییر میکند یا $\pm 2$ تغییر میکند. به همین دلیل، با افزودن یال، زوج ماندن تعداد رأسهای فرد حفظ میشود.
۶. جمعبندی
در این مقاله با مفهوم رأس فرد در گراف آشنا شدیم. دیدیم که بر اساس قضیه دست دادن، مجموع درجات همه رأسها زوج است و در نتیجه تعداد رأسهای فرد در هر گراف همواره زوج میباشد. رأسهای فرد نقش کلیدی در تعیین وجود مسیرهای اویلری دارند و در مسائل بهینهسازی شبکه مانند مسیریابی خودروها و طراحی شبکههای مخابراتی کاربرد دارند. شناسایی سیستماتیک این رأسها با شمردن درجه هر رأس انجام میشود و ویژگی زوج بودن تعداد آنها ابزاری برای بررسی درستی محاسبات فراهم میکند.
پاورقی
1 نظریه گراف (Graph Theory): شاخهای از ریاضیات گسسته که به مطالعه ساختارهای متشکل از رأس و یال میپردازد.
2 مسیر اویلری (Eulerian Path): مسیری در گراف که از هر یال دقیقاً یک بار عبور کند.
3 حلقه (Loop): یالی که یک رأس را به خودش متصل میکند و درجه آن رأس را به جای یک واحد، دو واحد افزایش میدهد.
