десно|оквир|Хамилтонов пут (црно) над графом (плаво). мини|Примери Хамилтонових циклуса на графу квадратне решетке 8х8. У области математике, теорији графова, Хамилтонов пут је пут у неусмереном графу који посећује сваки чвор тачно једном. Хамилтонов циклус је циклус у неусмереном графу који посећује сваки чвор тачно једном. Одређивање да ли такав пут или циклус постоје у датом графу је проблем Хамилтоновог пута. Овај проблем је НП-комплетан.
Хамилтонов пут и циклус су добили име по ирском математичару Вилијаму Роуану Хамилтону.
Ако је граф повезан и за свака два чвора u и v важи d(u) + d(v) ≥ n, где су d(u) и d(v) степени чворова u и v, a n укупан број чворова графа онда граф има Хамилтонов циклус одн. јесте Хамилтонов. Такође, ако је граф повезан и за сваки чвор u важи d(u) ≥ n/2 онда је граф Хамилтонов. Ако граф садржи мост онда нема Хамилтонов циклус. Ако у графу G, који је Хамилтонов, постоји чвор степена два тада обе гране инцидентне са њим морају бити део Хамилтоновог циклуса. Ако је граф бипартитан и Хамилтонов и скуп његових чворова се разбија на два дисјунктна скупа Х и Y онда важи |X|=|Y|.
Види још Ојлеров пут Проблем трговачког путника Ловасова конјектура
Референце
Категорија:Објекти теорије графова Категорија:НП-комплетни проблеми Категорија:Рачунарски проблеми у теорији графова