Гамильтонов путь. Решение/Гилязев Руслан — различия между версиями
Материал из DISCOPAL
Ruslan1 (обсуждение | вклад) |
Ruslan1 (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| − | Выберем произвольное ребро. Получим путь длины 1. Покажем как можно увеличить путь на 1. Пусть у нас имеется путь из 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. Покажем как можно увеличить путь на 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). |
[[Категория:Предложенные студентами задачи]] | [[Категория:Предложенные студентами задачи]] | ||
Версия 15:36, 3 июня 2015
Выберем произвольное ребро. Получим путь длины 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).