پیدا کردن مسیرهای همیلتونی بین دو راس معین در گراف‌های توری t شکل با اندازه زوج

یکی از مسایل مشهور در نظریه گراف، مساله مسیر یا دور همیلتونی است. این مساله برای گراف‌های عمومی و حتی برخی از کلاس‌های گراف‌ از جمله گراف‌های توری عمومی np کامل است. در این مقاله، مساله پیدا‌کردن مسیر همیلتونی بین دو راس ‏معین s و t در گرافهای توری t شکل با اندازه زوج، که حالت خاصی از گراف های توری است، بررسی می‌شود. این مساله کاربردهای مختلفی از جمله در ربات‌های جاروکننده و پردازش موازی دارد. در این مقاله، ابتدا شرایط لازم برای اینکه مسیر و دور همیلتونی وجود داشته باشد بیان می‌شود، سپس یک الگوریتم زمان خطی بر حسب اندازه گراف برای حل مساله مسیر و دور همیلتونی ارائه می‌شود.

finding hamiltonian paths between two given vertices in even sized t shaped grid graphs

one of the most popular problems in graph theory is the hamiltonian path or cycle problem. this problem is np complete for general graphs and even some classes of graphs, including general grid graphs. in this paper, we study the problem of finding a hamiltonian path between two given vertices s and t in even sized t shaped grid graphs, which is special case of grid graphs. this problem has many applications including in sweeping robots and in parallel processing. in this paper, first we give necessary conditions for the existence of hamiltonian paths and cycles, then we present a linear time algorithm for solving these problem.