Хамилтонов пут

Из Википедије, слободне енциклопедије
Хамилтонов пут (црно) над графом (плаво).

У области математике, теорији графова, Хамилтонов пут је пут у неусмереном графу који посећује сваки чвор тачно једном. Хамилтонов циклус је циклус у неусмереном графу који посећује сваки чвор тачно једном. Одређивање да ли такав пут или циклус постоје у датом графу је проблем Хамилтоновог пута. Овај проблем је НП-комплетан.

Хамилтонов пут и циклус су добили име по ирском математичару Вилијаму Роуану Хамилтону.

Ако је граф повезан и за свака два чвора 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]

Види још[уреди]

Референце[уреди]

  1. Стевановић, Драган; Ћирић, Мирослав; Симић, Слободан; Балтић, Владимир (2. 3. 2007). Дискретна математика: основе комбинаторике и теорије графова. стр. 257. 

Спољашње везе[уреди]