Хамилтонов пут — разлика између измена
Садржај обрисан Садржај додат
мНема описа измене |
Нема описа измене |
||
Ред 4:
Хамилтонов пут и циклус су добили име по ирском математичару [[Вилијам Роуан Хамилтон|Вилијаму Роуану Хамилтону]].
Ако је граф повезан и за свака два чвора u и v важи d(u) + d(v) ≥ n, где су d(u) и d(v) степени чворова u и v, a n укупан број чворова графа онда граф има Хамилтонов циклус одн. јесте Хамилтонов. Такође, ако је граф повезан и за сваки чвор u важи d(u)
Ако граф садржи мост онда нема Хамилтонов циклус. Ако у графу G, који је Хамилтонов, постоји чвор степена два тада обе гране инцидентне са њим морају бити део Хамилтоновог циклуса. Ако је граф бипартитан и Хамилтонов и скуп његових чворова се разбија на два дисјунктна скупа Х и Y онда важи |X|=|Y|.<ref>{{cite book|last1=Стевановић|first1=Драган|last2=Ћирић|first2=Мирослав|last3=Симић|first3=Слободан|last4=Балтић|first4=Владимир|title=Дискретна математика: основе комбинаторике и теорије графова|date=2. 3. 2007.|pages=257}}</ref>
| |||