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