Просмотр исходного текста страницы Гамильтонов путь. Решение/Гилязев Руслан

Выберем произвольное ребро. Получим путь длины 1.

Покажем как можно увеличить путь на 1.

Пусть у нас имеется путь T из k < n вершин. Пусть последняя вершина пути «b», а первая — «a». Возьмем любую вершину «c» не входящую в T. 
* Если есть ребро (b -> c) или ребро (c -> a), то мы сможем увеличить путь. 
* Если нет, то есть ребра (с -> b) и (a -> c). 
Тогда переберем все вершины из T. 

Очевидно, что найдется пара соседних вершин пути «u» и «v» (u — > v) такие, что есть ребра (u -> c) и (с -> v), тогда заменим (u -> v) этими ребрами. 

Итак, мы увеличили путь. Таким образом построим гамильтонов путь. Алгоритм работает за O(n²).

----
[[Участник:StasFomin|StasFomin]] ([[Обсуждение участника:StasFomin|обсуждение]]) 21:14, 3 июня 2015 (MSK):
Вот полный граф, без петель

<graph>
graph G{
 A--B--C--A
}
</graph>


Вот случайная ориентация

<graph>
digraph G{
  A->B->C
  A->C
}
</graph>

Где гамильтонов граф?

[[Category:Уже не исправить]]