سلام
مسئله ی وجود یک مسیر همیلتنی یک مسئله ی NP است (و NP_Complete است)
یعنی می توان آن را به صورت غیر قطعی در زمان چند جمله ای حل کرد و به قول سیپسر هیچ کس راه حلی در زمان چندجمله ای برای آن نمی داند.
و روش غیر قطعی آن بنابر گفته ی سیپسر این گونه است که ابتدا وجود مسیر بین این دو راس را به قطعی در زمان چندجمله ای با روش زیر تعیین کنیم:
اگر بخواهیم ببینیم آیا مسیری همیلتنی بین دو راس s و t در گراف G وجود دارد یا نه بدین صورت عمل می کنیم:
راس s را مارک کن
مادامی که راسی برای مارک کردن وجود نداشته باشد این کار را انجام بده: هر b ای که یک یال (a,b) موجود باشد و a مارک شده باشد را نیز مارک کن
اگر t مارک شده بود یعنی مسیری بین این دو راس وجود داشته

(واضح است که مرحله دوم نهایتا به تعداد رئوس تکرار می شود )

سپس چک کنیم که آیااین مسیر همیلتتنی است یا نه.

اثبات این مطالب را می توانید در صفحات ۲۶۰-۲۶۴و۲۸۶ کتاب سیپسر مطالعه کنید(شماره صفحات پی دی اف آن به ترتیب ۲۷۲-۲۷۶و ۲۹۸ است).
لینک کتاب سیپسر:

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.


اینم ۳ مقاله ی کوتاه در مورد این مسئله: