گراف همیلتونی (Hamiltonian Graph)، در ریاضیات (Mathematics)
انواع گراف همیلتونی (Hamiltonian Graph) را در آموزش زیر شرح دادیم :
گراف همیلتونی (Hamiltonian Graph) :
به طور کلی، یک گراف (Graph) را همیلتونی می گوییم اگر حداقل یک دور همیلتونی (Hamiltonian Cycle) داشته باشد. دور همیلتونی مسیری است بسته که از تمام رئوس (Vertices) گراف دقیقا یک بار عبور می کند و در نهایت به راس شروع بازمی گردد. به عبارت دیگر، این دور تمام رئوس گراف را پوشش می دهد. پیدا کردن اینکه آیا یک گراف دلخواه همیلتونی است یا نه، یکی از مسائل کلاسیک و دشوار در نظریه گراف ها محسوب می شود. شرط کافی برای وجود دور همیلتونی توسط قضیه (Theorem) معروف قضیه اور (Ore's Theorem) و قضیه دییرک (Dirac's Theorem) ارائه شده است. برای مثال، اگر در یک گراف ساده با n راس، مجموع درجات (Degrees) هر دو راس غیرمجاور حداقل n باشد، آن گراف همیلتونی است. مفهوم همیلتونی بودن برخلاف گراف های اویلری (Eulerian Graphs) که روی یال ها (Edges) تمرکز دارد، بر روی رئوس متمرکز است. کشف چنین دورهایی در مسائل بهینه سازی مانند مسئله فروشنده دوره گرد (Traveling Salesman Problem) کاربرد فراوانی دارد. گراف های کامل (Complete Graphs) مانند
\[ K_n \]برای
\[ n \geq 3 \]ساده ترین مثال از گراف های همیلتونی هستند. تشخیص همیلتونی بودن گراف های بزرگ با الگوریتم های ساده عملا غیرممکن است و از مسائل NP-Complete (ان پی-کامل) به شمار می رود.
