Икосианская игра

Игра

Уильям Роуэн Гамильтон — тот, что нацарапал на мосту кватернионы, — в 1856 году занимался «икосианским исчислением»: алгебраической системой с образующими и соотношениями, описывающей симметрии икосаэдра. По нынешним понятиям это одно из первых представлений группы образующими и соотношениями — тема, которую через полвека разовьёт Ден.

Из этой алгебры он извлёк головоломку. Возьмём додекаэдр — двенадцать пятиугольных граней, двадцать вершин. Требуется обойти все двадцать вершин, побывав в каждой ровно один раз и вернувшись в исходную.

ГамильтонУильям Роуэн Гамильтонирландский математик, физик и астроном · 1805–1865Пятнадцать лет искал, как умножать тройки чисел, и однажды на мосту в Дублине понял, что надо взять четвёрки и отказаться от коммутативности. оформил задачу как настольную игру, назвал «Икосианской» и продал права дублинскому издателю Джону Жаку за 25 фунтов. Игра вышла в 1859 году в двух вариантах — плоская доска с колышками и деревянный додекаэдр — и в продаже провалилась: покупатели быстро обнаруживали, что решение находится довольно легко, и интерес пропадал.

Двадцать пять фунтов остались единственными деньгами, которые Гамильтон заработал на математике.

Обманчивое сходство

Сравним с задачей о мостах, которая внешне почти такая же.

Разница выглядит пустяковой — рёбра вместо вершин, — а последствия катастрофические. Для эйлерова цикла есть критерий, проверяемый мгновенно. Для гамильтонова за сто семьдесят лет не найдено ничего похожего, и есть веские основания считать, что и не будет.

Почему так? Эйлеров цикл — локальное условие: достаточно посмотреть на каждую вершину отдельно и посчитать степень. Гамильтонов — глобальное: наличие цикла нельзя установить, изучая окрестности по одной; выбор в одной части графа связывает руки в другой.

Достаточные условия всё-таки известны, но они грубые. Теорема ДиракаПоль Дираканглийский физик-теоретик · 1902–1984Написал уравнение, из которого следовало существование античастиц, — и они нашлись. Ввёл дельта-функцию, которую математики двадцать лет считали недопустимой, а потом узаконили. (1952): если в графе на $n\geqslant3$ вершинах степень каждой вершины не меньше $n/2$, гамильтонов цикл есть. Условие сильное — оно требует, чтобы граф был очень плотным, — и большинства интересных случаев не покрывает.

Приоритет

Ради точности: почти одновременно с Гамильтоном ту же задачу поставил Томас Киркман — английский священник и математик-любитель, — причём в более общем виде: он спрашивал, для каких многогранников такой обход существует, и опубликовал это в 1856 году, на год раньше игры.

Киркман известен и другим: задачей о пятнадцати школьницах (1850) — как расставить пятнадцать девочек в пять троек на семь дней так, чтобы каждые двое оказались в одной тройке ровно раз. Задача породила целую область — теорию блок-схем и комбинаторных дизайнов, — а общий вопрос о существовании таких систем был закрыт только в 2014 году (Кивош и Питер Киван, независимо).

Имя, тем не менее, досталось Гамильтону — очередной случай закона Стиглера, которых на этой линии особенно много.

Что стало с задачей

В 1972 году Ричард Карп включил гамильтонов цикл в список двадцати одной NP-полной задачи. Это означает: если для него найдётся быстрый алгоритм, то быстрые алгоритмы появятся сразу у всех задач этого класса — и наоборот.

Практическое значение огромно. Ближайший родственник гамильтонова цикла — задача коммивояжёра: обойти города по разу с наименьшей суммарной длиной пути. Она возникает в логистике, в планировании производства, в разводке печатных плат, в геномном секвенировании. Точное решение для тысяч городов требует времени, несопоставимого с возрастом Вселенной; на практике пользуются приближёнными методами, дающими ответ в пределах пары процентов от оптимума.

Рекорд точного решения — 85 900 городов (задача разводки микросхемы, 2006 год), и на него ушли годы машинного времени.

Так салонная головоломка, проданная за двадцать пять фунтов и не окупившаяся, оказалась в центре главного открытого вопроса информатики.

Задача. Найдите гамильтонов цикл на графе куба (8 вершин, каждая соединена с тремя соседями). Затем объясните, почему на графе, у которого есть вершина степени 1, гамильтонова цикла быть не может.
(Указание: куб — это цикл длины 8, легко находится обходом «по спирали». Вершина степени 1 имеет единственное ребро; цикл должен войти в неё и выйти по разным рёбрам, а второго нет.)

Следующая точка: Кембридж — где докажут, что полного беспорядка не бывает, и сделают это мимоходом, в статье по логике.