Показать, что если язык "гамильтонов граф" принадлежит классу $%P$% (полиномиальный), то за полиномиальное время можно не только определить, что граф гамильтонов, но и найти в нем какой-нибудь гамильтонов цикл (если он существует).
Язык "гамильтонов граф": дан неориентированный граф, в котором есть гамильтонов цикл
Классу полиномиальных языков принадлежат языки, для которых существует машина Тьюринга, которая за полиномиальное по длине входа время останавливается и дает ответ "да", если на входе было слово из языка или дает ответ "нет" для слов, не принадлежащих языку.

задан 2 Май '16 0:26

10|600 символов нужно символов осталось
1

Рассмотрим произвольную вершину $%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$% операций, то есть всё укладывается в полиномиальную оценку.

ссылка

отвечен 2 Май '16 2:30

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×395
×169
×99
×35

задан
2 Май '16 0:26

показан
370 раз

обновлен
2 Май '16 2:30

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru