Гамильтонов путь. Решение/Гилязев Руслан — различия между версиями

Версия 18:14, 3 июня 2015

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

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

Пусть у нас имеется путь T из k < n вершин. Пусть последняя вершина пути «b», а первая — «a». Возьмем любую вершину «c» не входящую в T.

Тогда переберем все вершины из T.

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

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

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

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

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

@@ Строка 12: / Строка 12: @@
 Итак, мы увеличили путь. Таким образом построим гамильтонов путь. Алгоритм работает за 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:Проблемы в решении]]