Гамильтоновы пути и циклы
Нарисуйте пять точек по кругу, соедините каждую с двумя соседями — и вы сможете обойти каждую точку по разу и вернуться домой: это гамильтонов цикл. Добавьте несколько рёбер или уберите часть — и вопрос становится на удивление трудным. Есть ли у графа такой цикл — одна из самых известных задач, на которую ни один компьютер пока не умеет быстро отвечать для любого графа.
Каждая вершина по одному разу
Граф — это набор точек, вершин, соединённых линиями, рёбрами. Гамильтонов путь идёт по рёбрам и проходит через каждую вершину ровно один раз; гамильтонов цикл к тому же возвращается туда, где начался, поэтому у него столько же рёбер, сколько вершин. Граф с гамильтоновым циклом называют гамильтоновым. Проверить предложенный маршрут легко: сосчитайте вершины и посмотрите на каждый шаг. Трудное — найти такой маршрут или доказать, что его нет, ведь число порядков, в которых можно обойти вершины, растёт как n!, уже 2,4 × 10¹⁸ при 20 вершинах.
Икосиан Гамильтона
Уильям Роуэн Гамильтон, ирландский математик, открывший кватернионы, придумал игру «Икосиан» в 1857 году. На доске был изображён расплющенный на плоскости додекаэдр с 20 углами, помеченными согласными, а главная задача состояла в том, чтобы расставить по углам колышки с номерами от 1 до 20 так, чтобы соседние числа, а также 20 и 1, были соединены рёбрами. Права Гамильтон продал за 25 фунтов лондонскому производителю игрушек John Jaques and Son, который выпустил игру в 1859 году; продавалась она плохо. У головоломки 30 решений, если считать цикл один раз независимо от начала и направления. Сам вопрос был не нов: Томас Киркман в работе, отправленной в Королевское общество в 1855 году, спрашивал, у каких многогранников есть цикл через все их углы, и показал такой, у которого его нет.
Обходы конём
Обход конём передвигает шахматного коня так, чтобы он попал на каждое поле ровно один раз: это гамильтонов путь в графе, вершины которого — поля, а рёбра — ходы коня. Замкнутый обход заканчивается в одном ходе коня от начала, то есть является гамильтоновым циклом. Шахматисты ставили такие задачи более тысячи лет назад, а Эйлер изучал их в работе 1759 года. В 1823 году Х. К. фон Варнсдорф предложил всегда идти на поле с наименьшим числом дальнейших ходов; это простое правило обычно завершает обход доски 8 × 8 без возвратов. Конь всегда меняет цвет поля, поэтому замкнутому обходу нужно поровну светлых и тёмных полей, что исключает доски с нечётным числом полей. Аллен Швенк в 1991 году точно описал, у каких прямоугольных досок есть замкнутый обход; среди квадратных он есть у всякой с чётной стороной от 6. У обычной шахматной доски 13 267 364 410 532 замкнутых обхода — их сосчитал Брендан Маккей в 1997 году.
Графы без гамильтонова цикла
Самые быстрые доказательства того, что цикла нет, — это подсчёты. Если вершины можно раскрасить в два цвета так, чтобы каждое ребро соединяло разные цвета, то цикл чередует их и требует поровну вершин каждого цвета; у решётки 5 × 5 одного цвета 13, другого 12, значит, гамильтонова цикла нет. Точку сочленения, удаление которой разбивает граф, пришлось бы пройти дважды, а вершину степени 1 пройти нельзя вовсе. Некоторые графы ускользают от всех таких доводов. У графа Петерсена, опубликованного Юлиусом Петерсеном в 1898 году, 10 вершин степени 3 и нет гамильтонова цикла, и всё же удаление любой вершины оставляет граф, у которого он есть; это наименьший такой гипогамильтонов граф. Граф Хершеля, названный в честь Александра Стюарта Хершеля, писавшего об икосиане в 1862 году, имеет 11 вершин и 18 рёбер и является графом многогранника с девятью четырёхугольными гранями. Ни одному многограннику с меньшим числом углов гамильтонова цикла не недостаёт. В 1884 году Питер Гатри Тэт предположил, что гамильтонов цикл есть у каждого многогранника, в каждом углу которого сходятся три ребра; У. Т. Татт нашёл в 1946 году контрпример с 46 вершинами.
Условия, гарантирующие цикл
Если у графа много рёбер, гамильтонов цикл обеспечен. Габриэль Дирак доказал в 1952 году, что граф с n ≥ 3 вершинами, у которого каждая вершина имеет степень не меньше n/2, обладает таким циклом, а Эйстейн Оре ослабил условие в 1960 году: достаточно, чтобы у любых двух несмежных вершин сумма степеней была не меньше n. Оба условия работают лишь в одну сторону. Простое кольцо из 100 вершин имеет всюду степень 2, намного меньше 50, и всё же само является гамильтоновым циклом. Такова общая картина: есть достаточные условия и есть причины неудачи, а между ними лежит обширная область графов, о которых может судить лишь поиск.
Почему быстрой проверки не известно
Решить, есть ли у графа гамильтонов цикл, — NP-полная задача; она была одной из 21 задачи в списке Ричарда Карпа 1972 года. Метод, быстро решающий её для любого графа, быстро решал бы и тысячи других задач и закрыл бы вопрос P против NP. Контраст с эйлеровыми путями, которые проходят по каждому ребру один раз, разителен: Эйлер показал в 1736 году, что подсчёт вершин нечётной степени решает тот вопрос сразу. Лучшие точные методы для гамильтоновых циклов по-прежнему требуют экспоненциального времени. Динамическое программирование по всем подмножествам вершин, найденное Ричардом Беллманом, а также Майклом Хелдом и Ричардом Карпом в 1962 году, требует около n² × 2ⁿ шагов, а рандомизированный метод Андреаса Бьёрклунда 2010 года — около 1,657ⁿ. На практике поиск с возвратом и хорошим отсечением справляется с графами в несколько десятков вершин, а задача коммивояжёра, ищущая кратчайший гамильтонов цикл, — взвешенный вариант того же вопроса.
Коды Грея и гиперкуб
Запишите числа от 0 до 7 как 3-битные коды и соедините два кода, когда они отличаются ровно одним битом: получится граф куба. Гамильтонов цикл в нём, например 000, 001, 011, 010, 110, 111, 101, 100, перечисляет все восемь кодов так, что каждый отличается от предыдущего одним-единственным битом. Такой список и есть код Грея, названный в честь Фрэнка Грея из Bell Labs, описавшего его в патенте, поданном в 1947 году. Он есть у каждого гиперкуба: выпишите коды на один бит короче, затем тот же список задом наперёд, и припишите 0 перед первой половиной и 1 перед второй. Поворотные энкодеры используют коды Грея, чтобы показание, снятое между двумя положениями, никогда не ошибалось больше чем на один шаг. У куба 6 гамильтоновых циклов, у 4-битного гиперкуба — 1344.
Попробуйте сами
Откройте обозреватель гамильтоновых путей, чтобы самому взяться за головоломку Гамильтона: пунктирные кольца показывают, куда можно пойти. Либо перейдите в режим «Поиск» и посмотрите на работу поиска с возвратом: путь растёт, красные штрихи отмечают возвраты, а столбцы считают узлы по длине пути. Включайте и выключайте проверку тупиков, проверку связности и порядок Варнсдорфа, сравнивайте, сколько узлов нужно каждому варианту, считайте все циклы небольшого графа или нарисуйте свой граф и посмотрите, какие из быстрых проверок к нему применимы.
Часто задаваемые вопросы
Если у графа есть эйлеров цикл, будет ли он гамильтоновым, и наоборот?
Ни то, ни другое не следует одно из другого. У «бабочки», двух треугольников с общей вершиной, эйлеров цикл есть, потому что все степени чётные, а гамильтонова цикла нет, так как общую вершину пришлось бы пройти дважды. У полного графа K₄ есть гамильтоновы циклы, но все четыре вершины имеют степень 3, поэтому эйлерова цикла у него нет.
Разве компьютер не может просто перебрать все порядки?
Только для маленьких графов. Порядков из n вершин n!, при 20 это около 2,4 × 10¹⁸. Поиск с возвратом справляется куда лучше, потому что идёт только по рёбрам и бросает частичный путь, как только упрётся: все 30 циклов додекаэдра с 20 вершинами он находит примерно за 1400 шагов. Но для некоторых графов число частичных путей всё равно растёт экспоненциально, и метода, который избегал бы этого для любого графа, не известно.
Проще ли задача о гамильтоновом пути, чем о цикле?
Нет, обе NP-полные. Каждая сводится к другой: добавьте новую вершину, соединённую со всеми старыми, и у старого графа есть гамильтонов путь ровно тогда, когда у нового есть гамильтонов цикл. В обратную сторону задача о цикле превращается в задачу о пути: добавьте копию одной вершины с теми же соседями и прицепите новую концевую вершину к самой вершине, а ещё одну — к её копии.
Почему обход конём на доске 5 × 5 должен начинаться на цвете углов?
Из 25 полей 13 имеют цвет углов и 12 — другой, а конь меняет цвет при каждом ходе. Обход по 25 полям чередует цвета, поэтому он начинается и заканчивается на том цвете, полей которого больше. Приложение находит все 1728 открытых обходов доски 5 × 5, то есть 864, если обход и его обращение считать за один, и каждый начинается и заканчивается на поле цвета углов.
Готовы попробовать?
Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.
Открыть обозреватель гамильтоновых путей