Путь
Просмотрено узлов
Гамильтонов цикл
Гамильтонов путь

Режим

    Цель

    Подробнее о гамильтоновых путях и циклах

    Обозреватель гамильтоновых путей

    В 1857 году Уильям Роуэн Гамильтон придумал головоломку: пройти по рёбрам додекаэдра так, чтобы побывать в каждом из его 20 углов ровно один раз и закончить там, где начали. Такой маршрут сегодня называют гамильтоновым циклом. Проверить его легко, а найти, как правило, трудно. Пройдите один сами по додекаэдру Гамильтона, по шахматной доске или по графу, который нарисуете, либо посмотрите, как его ищет поиск с возвратом, сосчитайте тупики, в которые он попадает, и увидите, насколько несколько простых проверок сокращают поиск. Выберите граф и цель: цикл, возвращающийся в начало, или путь. Обход: щёлкните вершину, чтобы начать, затем по одному соседу за раз; пунктирные кольца показывают, куда можно пойти. Щелчок по последней вершине, «Назад» или «Отменить» возвращает на шаг, а «Подсказка» называет следующий шаг, который ещё можно довести до конца. Поиск: «Пуск» или «Шаг» запускает поиск с возвратом, который добавляет вершины, пока не упрётся, и тогда откатывается; красные штрихи показывают возвраты, а столбцы считают узлы по длине пути. До запуска щелчок по вершине выбирает, откуда он начнётся. Флажки включают и выключают отсечение, «Сравнить» запускает тот же поиск с ним и без него, а «Сосчитать все» считает каждый цикл или путь небольшого графа. Правка: щёлкните, чтобы добавить вершину, щёлкните две вершины, чтобы соединить или разъединить их, перетащите, чтобы передвинуть одну, а «Удалить» убирает выбранную вершину.

    Как это работает

    1. Выберите граф, например додекаэдр Гамильтона, граф Петерсена или обход конём, либо нарисуйте свой в «Правке», и выберите целью цикл или путь.
    2. В режиме «Обход» щёлкните вершину, чтобы начать, а затем соседей одного за другим. «Назад» и «Отменить» возвращают на шаг, а «Подсказка» показывает следующий шаг, который ещё можно довести до конца.
    3. В режиме «Поиск» нажмите «Пуск» или «Шаг», чтобы посмотреть, как поиск с возвратом ищет маршрут, включайте и выключайте отсечение и нажмите «Сравнить», чтобы увидеть, сколько узлов нужно каждому варианту.

    Гамильтон против Эйлера

    Эйлеров путь проходит по каждому ребру один раз; гамильтонов путь — через каждую вершину один раз. Звучит похоже, а ведёт себя совсем иначе. Есть ли у связного графа эйлеров путь, решается подсчётом вершин нечётной степени, как показал Эйлер в 1736 году: он есть, когда таких вершин нет или их две. Для гамильтоновых путей подобного правила не известно. Решить, есть ли у графа гамильтонов цикл, — NP-полная задача, одна из 21 задачи в списке Ричарда Карпа 1972 года, так что быстрый метод для неё дал бы быстрые методы для тысяч других трудных задач. Зато есть условия, решающие дело для части графов. Теорема Дирака 1952 года гарантирует гамильтонов цикл, когда каждая вершина имеет степень не меньше n/2, а теорема Оре 1960 года — когда у любых двух несмежных вершин сумма степеней не меньше n; вершина степени 1, точка сочленения или два цветовых класса разного размера его исключают.

    Как работает поиск

    Поиск с возвратом строит путь по одной вершине и, упёршись, забирает последний шаг назад и пробует следующего соседа. Он всегда найдёт гамильтонов цикл, если тот есть, но число частичных путей может расти экспоненциально. На решётке 5 × 5, у которой гамильтонова цикла нет, обычный поиск с возвратом просматривает 153 745 узлов, прежде чем убедится в этом. Две проверки рано обрывают безнадёжные пути: непосещённая вершина, у которой меньше двух свободных соседей, в цикл уже не встроится, а когда непосещённые вершины распадаются на отдельные части, ни один единый путь их не покроет. С обеими то же доказательство занимает 1761 узел. Правило Варнсдорфа 1823 года, которое сначала пробует соседа с наименьшим числом дальнейших ходов, находит обход конём на доске 8 × 8 из угла за 64 хода без единого тупика.

    Часто задаваемые вопросы

    Чем гамильтонов путь отличается от гамильтонова цикла?

    Гамильтонов путь проходит через каждую вершину графа ровно один раз. Гамильтонов цикл делает то же самое и ещё по одному ребру возвращается туда, где начался, поэтому он может начинаться в любой своей вершине. У всякого графа с гамильтоновым циклом есть и гамильтонов путь (уберите одно ребро цикла), но не наоборот: у графа Петерсена есть гамильтоновы пути и нет гамильтонова цикла.

    Есть ли у додекаэдра гамильтонов цикл?

    Да, их 30, если считать каждый цикл один раз независимо от начала и направления. В 1857 году Гамильтон превратил это в игру «Икосиан»: доска с 20 углами расплющенного додекаэдра, помеченными согласными. Права он продал за 25 фунтов лондонскому производителю игрушек John Jaques and Son. «Сосчитать все» находит эти 30 циклов примерно за 1400 узлов.

    Почему у решётки 5 × 5 нет гамильтонова цикла?

    Раскрасьте 25 точек как шахматную доску: 13 получат один цвет, 12 — другой, и каждый шаг ведёт к другому цвету. Цикл чередует цвета по всему кругу, поэтому ему нужно поровну того и другого, а 13 и 12 этого не дают. Тот же довод годится для любой решётки с нечётным числом точек, для коня на доске 5 × 5 или 7 × 7 (конь всегда меняет цвет поля) и для графа Хершеля, у которого в двух классах 6 и 5 вершин. Гамильтонов путь при этом возможен: он начинается и заканчивается на более многочисленном цвете.

    Как правило Варнсдорфа находит обход конём?

    Х. К. фон Варнсдорф предложил в 1823 году всегда переводить коня на то поле, с которого у него будет меньше всего дальнейших ходов. Поля у краёв и в углах, которые легко отрезать, посещаются благодаря этому рано, пока конь ещё может на них попасть. Правило — эвристика, а не гарантия, и ничьи приходится как-то разрешать, но на доске 8 × 8 оно обычно завершает обход без возвратов. В сочетании с поиском с возвратом, как в этом приложении, оно находит открытые обходы начиная с 5 × 5 и замкнутые на досках 6 × 6 и 8 × 8.

    Сколько гамильтоновых циклов у полного графа?

    (n − 1)!/2 при n ≥ 3. Закрепите начальную вершину; остальные n − 1 могут идти в любом порядке, и каждый цикл считается дважды, по разу на направление. У K₆ их 5!/2 = 60, у K₁₀ — 181 440. Именно из таких маршрутов выбирает коммивояжёр, и потому перебрать их все так быстро становится невозможно.

    Готовы попробовать?

    Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.

    Перейти в редактор