مسیر و دور اویلری؛ شرط درجهها و همبندی گراف
آموزش تشخیص مسیر اویلری و دور اویلری با درجه رأسها، همبندی و روش ساخت مسیر در تست گراف.
پاسخ کوتاه
مسیر اویلری هر یال را دقیقاً یک بار طی میکند؛ ممکن است رأسها تکرار شوند. برای تشخیص وجود چنین مسیری لازم نیست همه مسیرها را امتحان کنیم. همبندی بخش دارای یال و تعداد رأسهای درجه فرد پاسخ را تعیین میکند.
مسیر و دور
مسیر اویلری از هر یال دقیقاً یک بار میگذرد. اگر نقطه شروع و پایان یکی باشد، دور اویلری داریم. این مفهوم با مسیر همیلتونی متفاوت است؛ در همیلتونی هدف دیدن هر رأس یک بار است، نه استفاده یکباره از هر یال.
شرط همبندی
همه رأسهایی که درجه مثبت دارند باید در یک مؤلفه همبند باشند. رأسهای منفردِ درجه صفر برای پیمایش یالها مانع نیستند. اگر یالها در دو بخش جدا قرار گرفته باشند، یک مسیر پیوسته نمیتواند همه آنها را پوشش دهد.
شرط دور اویلری
یک گراف بدون جهت همبندِ دارای یال دور اویلری دارد اگر و تنها اگر درجه همه رأسها زوج باشد. ورود به هر رأس باید با خروج از آن جفت شود و چون شروع و پایان یک نقطهاند، در رأس آغاز نیز درجه زوج لازم است.
شرط مسیر باز
اگر دقیقاً دو رأس درجه فرد باشند، مسیر اویلری باز وجود دارد و باید از یکی از رأسهای فرد شروع و در دیگری تمام شود. اگر تعداد رأسهای فرد بیشتر از دو باشد، مسیر اویلری وجود ندارد. صفر رأس فرد حالت دور بسته است.
مثال و تست کوتاه
گرافی با درجات 1، 2، 2، 3 در صورت همبندبودن مسیر اویلری باز دارد، چون دقیقاً دو درجه فرد یعنی 1 و 3 دیده میشود. مسیر باید از یکی از همان دو رأس آغاز و در دیگری پایان یابد و نمیتواند دور اویلری باشد.
چکلیست حل تست
- مسیر اویلری یالها را یکبار مصرف میکند.
- صفر رأس فرد یعنی امکان دور اویلری.
- دو رأس فرد، ابتدا و انتهای مسیر باز هستند.