Хамилтонов пут
У области математике, теорији графова, Хамилтонов пут је пут у неусмереном графу који посећује сваки чвор тачно једном. Хамилтонов циклус је циклус у неусмереном графу који посећује сваки чвор тачно једном. Одређивање да ли такав пут или циклус постоје у датом графу је проблем Хамилтоновог пута. Овај проблем је НП-комплетан.
Хамилтонов пут и циклус су добили име по ирском математичару Вилијаму Роуану Хамилтону.
Ако је граф повезан и за свака два чвора 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.
