مسئله طولانی ترین مسیر در گراف های توری T- شکل با اندازه زوج

مسئله طولانی ترین مسیر، مسئله یافتن مسیری ساده با بیشترین تعداد راس بین دو راس معین در گراف است. این مسئله یکی از مسائل ان پی سخت مشهور در نظریه گراف است. مسئله ای در رده پی است اگر در مان چند جمله ای قابل حل باشد. مسئله ای در رده ان پی است که در زمان چند جمله ای قابل راستی آزمایی باشد، یعنی با داشتن یک جواب بالقوه بتوان در زمان چندجمله ای راستی آزمایی کنیم که این جواب واقعا یک جواب درست برای مسئله است یا خیر. مسئله ان پی سخت مسئله ای است که همه مسائل ان پی را بتوان در زمان چند جمله ای به آن کاهش داد. مسئله A به مسئله B کاهش می یابد اگر بتوان هر نمونه از مسئله A را به یک نمونه از مسئله B تبدیل کرد و از روی جواب مسئله B بتوان جواب مسئله A را به دست آورد. مسئله مسیر همیلتونی، یعنی تصمیم گیری در مورد این که آیا مسیری ساده بین دو راس معین در گراف وجود دارد که هر راس دقیقا یک بار ملاقات شود، حالت خاصی از مسئله طولانی ترین مسیر است. این مسئله کاربرد های زیادی در طراحی تراشه های VLSI، تجسم اطلاعات، روباتیک و غیره دارد ]۱[ و تنها برای رده های خاصی از گراف الگوریتم زمان چندجمله ای ارائه شده است ]۲[ و هنوز برای برخی از انواع رده های گراف این مسئله باز است ]۳[. گراف توری اولین بار در سال ۱۹۷۸ توسط لوسیو و موگنیا معرفی شد ]۴[. ایتای و همکارانش ]۵[ ثابت کردند که مسئله مسیر همیلتونی برای گراف های توری عمومی ان پی کامل است، آن ها همچنین مسئله مسیر همیلتونی بین دو راس معین در گراف های توری مستطیلی را حل کردند. چن و همکارانش ]۶[ الگوریتمی موازی برای ساختن مسیر همیلتونی در گراف توری مستطیلی ارائه کردند. چانگ و همکارانش ]۷[ مسئله طولانی ترین مسیر بین دو راس معین که دقیقا یک راس از گراف توری مستطیلی حذف شده باشد را حل کردند. هیدارا و همکارانش ]۸[ مسئله طولانی ترین مسیر بین دو راس معین که دقیقا دو راس از گراف توری مستطیلی حذف شده باشد را حل کردند

Keywords:

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