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

Материал из DISCOPAL
Перейти к: навигация, поиск
(Массовая правка: замена :Проблемы в решении]] на :Уже не исправить]])
 
(не показаны 2 промежуточные версии этого же участника)
Строка 1: Строка 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^2).  
+
Покажем как можно увеличить путь на 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): Вот полный граф, без петель

[svg]


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

[svg]

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

Источник — «https://discopal.ispras.ru/index.php?title=Гамильтонов_путь._Решение/Гилязев_Руслан&oldid=11254»