گراف همیلتونی (Hamiltonian Graph)، در ریاضیات (Mathematics)

انواع گراف ها (Graph) را در آموزش زیر شرح دادیم :

گراف همیلتونی (Hamiltonian Graph) :

یک گراف همیلتونی گرافی است که دارای یک "دور همیلتونی" (Hamiltonian Cycle) باشد. دور همیلتونی مسیری بسته در گراف است که دقیقا یک بار از هر راس گراف عبور می کند و در نهایت به راس شروع بازمی گردد. به عبارت دیگر، یک گشت دورانی که از همه شهرها (رئوس) دقیقا یک بار دیدن کند. یافتن اینکه آیا یک گراف دلخواه همیلتونی است یا نه، یکی از مسائل NP-کامل در علوم کامپیوتر است، به این معنی که الگوریتم کارآمدی برای حل آن برای همه گراف ها یافت نشده است. این مسئله ارتباط مستقیمی با مسئله فروشنده دوره گرد دارد، با این تفاوت که در مسئله فروشنده دوره گرد، گراف وزندار است و هدف یافتن کوتاه ترین دور همیلتونی است.