مسیر همیلتونی

در نظریه گراف، مسیر همیلتونی مسیری در یک گراف غیرجهت‌دار است که هر راس را دقیقا یک بار مشاهده می‌کند. مدار همیلتونی (یا دور همیلتونی) مداری در یک گراف جهت‌دار است که دقیقا یک بار هر راس را مشاهده کرده و همچنین به راس آغازین برمی گردد.
مسیر و مدار همیلتونی به نام ویلیام رومن همیلتون* نام گذاری شده‌اند. ویلیام همیلتون بازی ایکوسیان را، که امروزه به نام پازل همیلتون معروف است اختراع کرد. این بازی شامل یافتن یک مدار همیلتونی در گراف یالی یک دوازده سطحی است.

تعاریف

شکل (1)
مداری همیلتونی در یک گراف(رنگ قرمز)

شکل (2)
مسیری همیلتونی(آبی) در یک گراف(مشکی)

شکل (3)
گراف همیلتون

مسیر همیلتونی

یک مسیر همیلتونی یا مسیر قابل تعقیب، مسیری است که هر راس را دقیقا یک بار مشاهده کند. گرافی را که دارای مسیر همیلتنی باشد، گراف قابل تعقیب یا نیمه همیلتنی می‌نامند. هم چنین گرافی همیلتن-متصل است اگر برای هر زوج از رئوس آن، مسیری همیلتونی بین آن دو راس وجود داشته باشد.

مدار همیلتونی

مدار همیلتونی یا دور همیلتونی، مداری است که هر راس را دقیقا یک بار مشاهده می‌کند.(به جز راسی که هم به عنوان آغاز و هم پایان می‌باشد. در نتیجه این راس دو بار دیده می‌شود.) به طور قراردادی، گرافی کوچک شامل یک گره، دارای مدار همیلتونی است، ولی گراف متصلی دارای دو گره، شامل مدار همیلتونی نیست.

گراف همیلتونی

گرافی که دارای مدار همیلتونی باشد، گراف همیلتونی نامیده می‌شود. هر گراف کامل که بیشتر از دو راس داشته باشد، همیلتونی است.
گرافی با نام گراف همیلتون وجود دارد که یک دوازده وجهی منتظم است و دارای دورهای همیلتونی زیبا می‌باشد.(شکل(۳))

مدار همیلتونی مساله‌ای از نوع NP

مسئله فروشنده دوره‌گرد برای دانشمندانی که روی مسائل NP کار می‌کنند، بسیار آشناست. صورت این مساله به این گونه‌است که فرض کنید فروشنده دوره گردی داریم که می‌خواهد برای فروش کالاهای خود، به چند شهر سفر کند. فرض کنید بین این چند شهر راه‌های مختلفی با طول مسیرهای مختلفی وجود دارد. حال این فروشنده دوره گرد از چه راه‌هایی برود تا همه شهرها را یکبار بپیماید، و در کوتاه‌ترین مسیر حرکت کرده و در کمترین زمان به شهر اولی که از آن شروع کرده بود برسد. این مساله ابتدا به صورت ریاضی مدل می‌شود و تبدیل به مساله مدار همیلتونی در علم ریاضی و نظریه گراف‌ها می‌شود و سپس برای حل آماده می‌گردد. بسیاری از دانشمندان برای حل مسائل NP بیشتر روی مساله فروشنده دوره گرد کار می‌کنند.
تعیین شرط یا شروط لازم و کافی برای وجود داشتن مسیر یا دور همیلتونی در یک گراف هنوز به عنوان یک مساله لاینحل باقی مانده‌است، ولی شروط لازم خوبی وجود دارند که به صورت قضیه مطرح شده‌اند. همچنین الگوریتمی احتمالی که توسط آقای ویلف(۱۹۹۴) شرح داده شده‌است، می‌تواند برای یافتن مسیر و مدار همیلتنی مفید باشد.

خواص و قضایا

هر مدار همیلتونی می‌تواند با حذف یکی از یال‌هایش به یک مسیر همیلتونی تبدیل شود. اما یک مسیر همیلتونی زمانی می‌تواند به یک مدار همیلتونی توسعه یابد که نقاط انتهایی آن مجاور و همسایه باشند.
گراف خط یک گراف همیلتونی، خود همیلتونی است. همچنین گراف خط یک گراف اویلری نیز همیلتونی است.
همان طور که ذکر شد شرط لازم و کافی برای گفتن همیلتونی بودن یک گراف هنوز یافت نشده‌است. ولی دو قضیه زیر شرظ خوبی برای همیلتونی بودن یک گراف هستند.
قضیه : اگر G یک گراف ساده با ۳<=n راس باشد و اگر برای هر دو راس نا مجاور u,v داشته باشیم deg(u) + deg(v) => n، آنگاه گراف G هامیلتونی است.
قضیه دیراک: اگر در گراف ساده و همبند G با ۳<=n راس داشته باشیم d|v| => n/۲ (که V راس دلخواه از G است.) آنگاه گراف G همیلتونی است.

منابع

• ویکی‌پدیای انگلیسی، مسیر همیلتونی
• گراف‌های همیلتونی
• NP مسائل
• Paths and Circuits
• Hamiltonian Cycle -- from Wolfram MathWorld

در ویکی‌انبار پرونده‌هایی دربارهٔ مسیر همیلتونی موجود است.