علوم رایانش و فناوری اطلاعات
الگوریتم زمان خطی برای پیدا کردن مسیر همیلتونی در گراف توری L-شکل با یک حفره‌ی مستطیلی با اندازه فرد
نوع مقاله : مقاله پژوهشی
نویسندگان
1 دانشگاه شاهد، تهران، ایران, دانشکده علوم پایه، دانشگاه شاهد، تهران، ایران
2 دانشکده علوم پایه، دانشگاه شاهد، تهران، ایران
چکیده
مسیر همیلتونی در بسیاری از حوزه‌ها از جمله ریاضیات و صنعت کاربردهای زیادی دارد. مسیر همیلتونی، مسیری در گراف است، به طوری که هر رأس دقیقا یکبار در آن ملاقات می‌شود. ثابت شده است که مسأله‌ی پیدا کردن مسیر همیلتونی در گراف‌های عمومی، ان‌پی-کامل است. همچنین برای گراف‌های توری عمومی نیز این مسأله در دسته‌ی مسا‌ئل ان‌پی-کامل قرار می‌گیرد. در این مقاله، این مسأله را برای زیر کلاس خاصی از گراف‌های توری، به نام گراف توری L-شکل با یک حفره مستطیلی که اندازه کل گراف فرد است، حل کرده‌ایم و شرایط لازم و همچنین الگوریتم ساخت مسیر را ارائه داده‌ایم. در نهایت نشان داده‌ایم که این الگوریتم در زمان خطی مسیر همیلتونی بین دو رأس معین s و t در این گراف‌ها را به دست می‌‌آورد.
کلیدواژه‌ها
)