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