پيدا كردن مسيرهاي هميلتوني بين دو رأس معين در گراف‌هاي توري T شكل با اندازه زوج

يكي از مسايل مشهور در نظريه گراف، مسأله مسير يا دور هميلتوني است. اين مسأله براي گراف‌هاي عمومي و حتي برخي از كلاس‌هاي گراف‌ از جمله گراف‌هاي توري عمومي NP كامل است. در اين مقاله، مسأله پيدا‌كردن مسير هميلتوني بين دو رأس ‏معين s و t در گرافهاي توري T شكل با اندازه زوج، كه حالت خاصي از گراف هاي توري است، بررسي مي‌شود. اين مسأله كاربردهاي مختلفي از جمله در ربات‌هاي جاروكننده و پردازش موازي دارد. در اين مقاله، ابتدا شرايط لازم براي اينكه مسير و دور هميلتوني وجود داشته باشد بيان مي‌شود، سپس يك الگوريتم زمان خطي بر حسب اندازه گراف براي حل مسأله مسير و دور هميلتوني ارائه مي‌شود.