‫ الگوریتم زمان خطی برای پیدا کردن مسیر همیلتونی در گراف توری L-شکل با یک حفره‌ی مستطیلی با اندازه فرد

الگوریتم زمان خطی برای پیدا کردن مسیر همیلتونی در گراف توری L-شکل با یک حفره‌ی مستطیلی با اندازه فرد

مهران زالی‌قهی, فاطمه کشاورز‌کوهجردی

چکیده

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


کلمات کلیدی

مسیر همیلتونی, دور همیلتونی, گراف توری, گراف توری L-شکل با یک حفره مستطیلی, ان‌پی-کامل

مراجع