графы - Гамильтонов граф

Рассмотрим произвольную вершину $%v_1$%. Через неё проходит какой-то гамильтонов цикл. Перебираем последовательно все рёбра, выходящие из $%v_1$%. Если через одно из них проходит гаимльтонов цикл, то он имеется в графе, в котором это ребро стянули в точку. Каждый такой граф подаём на вход алгоритма полиномиальной сложности. За M шагов, где M -- максимальная степень вершины графа, мы узнаём ответ (в виде ребра, через которое надо идти).

Теперь по индукции строим путь $%v_1 - v_2 - \cdots - v_k$%. Пусть нам известно, что имеется гамильтонов путь с данным началом. Проверяем все рёбра, выходящие из $%v_k$% в какую-то из новых вершин. Это требует не более M проверок. Для каждого ребра $%v_k - v_{k+1}$% мы рассматриваем граф, в котором $%v_1$% и $%v_{k+1}$% отождествлены, а промежуточные вершины удалены (вместе с инцидентными им рёбрами). Подаём такой граф на вход алгоритма, и на одном из шагов имеем успех. Тогда путь продолжается на одно ребро. Когда доходим до последней вершины графа, остаётся дополнить путь до цикла.

Число "больших" шагов равно числу вершин, то есть полиномиальное количество проверок (размер графа, подаваемого на вход, всегда не больше исходного) для каждого из отдельных испытаний, не превосходящее $%N^c$%, умножается на $%Mn$%, и итоговое число шагов для нахождения гамильтонова цикла не больше $%N^{c+2}$%. Преобразование исходного графа в новый, с отождествлением двух вершин и удалением нескольких промежуточных, требует не более $%N^2$% операций, то есть всё укладывается в полиномиальную оценку.