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

Выберем произвольное ребро. Получим путь длины 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).

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.