مسیر همیلتونی را از اویلری جدا کن
مسیر همیلتونی هر رأس را دقیقاً یکبار میبیند و لازم نیست همهٔ یالها را مصرف کند. مسیر اویلری هر یال را یکبار طی میکند و میتواند به یک رأس بازگردد. نخست کمیت «رأس یا یال» را از متن سؤال مشخص کن.
همهٔ رأسها حضور دارند؟ | هیچ رأس تکرار نشده؟ | هر دو رأس پیاپی مجاورند؟ | برای دور، ابتدا و انتها مجاورند؟
دور همیلتونی یک شرط اضافه دارد
در دور، پس از دیدن همهٔ رأسها باید از آخرین رأس با یک یال به رأس آغاز برگردی. تکرار رأس آغاز در انتهای نوشتار فقط برای بستن نمایش دور است و به معنای بازدید دوبارهٔ مستقل نیست.
رأس درجهٔ یک را سریع بررسی کن
گراف دارای رأس درجهٔ یک نمیتواند دور همیلتونی داشته باشد، چون آن رأس برای ورود و خروج در دور به دو یال نیاز دارد. با این حال ممکن است در مسیر باز، رأس درجهٔ یک یکی از دو انتها باشد.
رأسهای کمدرجه را زود جایگذاری کن
رأسی با تنها دو همسایه در یک دور همیلتونی مجبور است از هر دو یال مربوط استفاده کند. این اجبارها را پیش از انتخاب آزادانهٔ یالها ثبت کن تا بنبستهای بعدی کمتر شود.
رأس برشی را برای دور تحلیل کن
اگر حذف یک رأس گراف را به بخشهای جدا تبدیل کند، وجود دور همیلتونی با مانع جدی روبهروست؛ دور باید بتواند بدون بازدید دوبارهٔ آن رأس میان بخشها حرکت کند. استدلال را روی اجزای حاصل نشان بده.
نمونهٔ ساخت مسیر
اگر یالهای لازم میان ترتیب A–B–D–C وجود داشته باشند و این چهار رأس کل گراف باشند، این ترتیب یک مسیر همیلتونی است. برای دور باید یال C–A نیز وجود داشته باشد.
از اجبارها شروع و سپس شاخهزنی کن
یالهای اجباری رأسهای کمدرجه را انتخاب کن. سپس در یک رأس با چند انتخاب، یکی را موقتاً بگیر و ادامه بده. اگر پیش از پوشش همهٔ رأسها دور کوچک یا بنبست ساختی، به آخرین انتخاب برگرد.
دور کوچک زودرس را حذف کن
اگر زیرمجموعهای از رأسها پیش از ورود دیگر رأسها یک دور بسته بسازد، آن انتخاب نمیتواند بخشی از دور همیلتونی نهایی باشد؛ مگر اینکه همان زیرمجموعه کل رأسها باشد.
نبود یک شرط ساده، همیشه حکم قطعی نمیدهد
برخلاف مسئلهٔ اویلری، یک معیار درجهای ساده و کامل برای همهٔ گرافها در این سطح نداریم. شرطهای لازم را برای ردکردن و جستوجوی منظم را برای ساختن به کار ببر؛ ادعای وجود را با ارائهٔ مسیر ثابت کن.
کنترل نهایی با فهرست رأسها
تعداد نامهای فهرستشده را با تعداد رأسها مقایسه و مجاورت هر جفت را از شکل یا ماتریس بررسی کن. برای تفاوت یالمحور از مسیر اویلری و برای مجاورت از ماتریس مجاورت کمک بگیر.