Гамильтонов путь. Решение/Гилязев Руслан — различия между версиями
Материал из DISCOPAL
Ruslan1 (обсуждение | вклад) |
StasFomin (обсуждение | вклад) (Массовая правка: замена :Проблемы в решении]] на :Уже не исправить]]) |
||
(не показаны 3 промежуточные версии 2 участников) | |||
Строка 1: | Строка 1: | ||
+ | Выберем произвольное ребро. Получим путь длины 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:Уже не исправить]] |
Текущая версия на 20:50, 20 мая 2020
Выберем произвольное ребро. Получим путь длины 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 (обсуждение) 21:14, 3 июня 2015 (MSK): Вот полный граф, без петель
Вот случайная ориентация
Где гамильтонов граф?