حمید در حال مطالعه روی گراف‌هایی است که می‌توانیم در آن‌ها دور همیلتونی را با زمان چند جمله‌ای پیدا کنیم. پس از بررسی‌های بسیار او به این نتیجه می‌رسد که اگر وجود تعدادی از زیرگراف‌های القایی ‎۴‎ راسی را در گراف مورد بررسی ممنوع کند، می‌تواند همیلتونی بودن گراف را با الگوریتمی سریع مشخص کند. او وجود ۳‎ دسته از گراف‌های ‎۴‎ راسی را در زیرگراف‌های القایی گراف مورد بررسی، ممنوع می‌کند:

• ‎‎ ستاره‌ی ‎۴‎ راسی
• مسیر ۴‎ راسی
• ‎‎ خوشه ۴‎ راسی

حال حمید می‌خواهد الگوریتمی از ‎$O(e)$‎ ارائه کند که در گراف‌های همبند با این ویژگی‌ها، در صورت وجود یک دور همیلتونی پیدا کند و در صورتی که گراف همیلتونی نیست، این موضوع را اعلام کند. ($e$‎ تعداد یال‌های گراف است.)

• سوال بعد
• سوال قبل