Хамилтонов пут
![](http://upload.wikimedia.org/wikipedia/commons/f/fc/Hamilton_path.gif)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/9/93/%D0%9D%D0%B0%D1%82%D1%83%D1%80%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D0%B3%D0%B0%D0%BC%D0%B8%D0%BB%D1%8C%D1%82%D0%BE%D0%BD%D0%BE%D0%B2%D1%8B%D1%85_%D1%86%D0%B8%D0%BA%D0%BB%D0%BE%D0%B2.jpg/220px-%D0%9D%D0%B0%D1%82%D1%83%D1%80%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D0%B3%D0%B0%D0%BC%D0%B8%D0%BB%D1%8C%D1%82%D0%BE%D0%BD%D0%BE%D0%B2%D1%8B%D1%85_%D1%86%D0%B8%D0%BA%D0%BB%D0%BE%D0%B2.jpg)
У области математике, теорији графова, Хамилтонов пут је пут у неусмереном графу који посећује сваки чвор тачно једном. Хамилтонов циклус је циклус у неусмереном графу који посећује сваки чвор тачно једном. Одређивање да ли такав пут или циклус постоје у датом графу је проблем Хамилтоновог пута. Овај проблем је НП-комплетан.
Хамилтонов пут и циклус су добили име по ирском математичару Вилијаму Роуану Хамилтону.
Ако је граф повезан и за свака два чвора u и v важи d(u) + d(v) ≥ n, где су d(u) и d(v) степени чворова u и v, a n укупан број чворова графа онда граф има Хамилтонов циклус одн. јесте Хамилтонов. Такође, ако је граф повезан и за сваки чвор u важи d(u) ≥ n/2 онда је граф Хамилтонов. Ако граф садржи мост онда нема Хамилтонов циклус. Ако у графу G, који је Хамилтонов, постоји чвор степена два тада обе гране инцидентне са њим морају бити део Хамилтоновог циклуса. Ако је граф бипартитан и Хамилтонов и скуп његових чворова се разбија на два дисјунктна скупа Х и Y онда важи |X|=|Y|.[1]
Види још[уреди | уреди извор]
Референце[уреди | уреди извор]
- ^ Стевановић, Драган; Ћирић, Мирослав; Симић, Слободан; Балтић, Владимир (2. 3. 2007). Дискретна математика: основе комбинаторике и теорије графова. стр. 257.