Том 11. Карты метро и нейронные сети. Теория графов

Представьте себе добросовестного почтальона, которому нужно обойти все улицы, где проживают адресаты писем. Оптимальным для него будет такой маршрут, при котором ему придется пройти по каждой улице ровно один раз. Если мы изобразим улицы на графе, то эта задача будет равносильна поиску эйлерова цикла в этом графе. Но если этот граф не содержит эйлеров цикл, почтальону придется пройти по некоторым улицам несколько раз, но так, чтобы число повторов было минимальным. Этой задачей занимался китайский математик Мэй-Ку Куан в 1962 году, поэтому она получила название задачи о китайском почтальоне.

Если мы внимательно посмотрим на рисунки выше, то увидим, что две вершины имеют степень, равную 3. Следовательно, данный граф не содержит эйлеров цикл. Однако на втором рисунке видно, что если мы добавим всего одно ребро (выделено пунктиром), то граф будет содержать эйлеров цикл (последовательность обхода ребер обозначена цифрами). При этом нужно будет пройти два раза всего по одной улице (5 и 6). Именно так выглядит алгоритм решения задачи китайского почтальона: если граф не содержит эйлеров цикл, нужно добавить к нему минимально возможное число ребер, которые будут дублировать уже имеющиеся, чтобы получить эйлеров цикл.

На следующих рисунках приведен один из возможных вариантов решения и оптимальный путь почтальона.

Эта задача широко применяется при доставке разнообразных грузов. Поиск оптимальных маршрутов в крупных городах представляет особый интерес, так как позволяет снизить финансовые и трудовые затраты при уборке улиц, доставке различных товаров и в других процессах. К счастью, в настоящее время при поиске таких маршрутов нам помогают компьютеры.

Гамильтоновы циклы

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

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

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

* * *

ИЗОБРЕТЕНИЕ ЦЕНОЙ В ДВЕ ГИНЕИ

Подобные циклы на графах открыл Томас Киркман (1806–1895). Исследованием этих циклов занимался ирландский математик Уильям Роуан Гамильтон (1805–1865), он же сделал их широко известными. В 1859 году Гамильтон придумал такую игру: 20 вершин додекаэдра (правильного 12-гранника) соответствуют 20 городам. Нужно обойти все города по одному разу и при этом вернуться в тот же город, с которого началось путешествие. Восторженный Гамильтон продал идею производителю игрушек за смехотворную сумму в две гинеи. Блестящие идеи не всегда ценятся по достоинству!

Математик Уильям Роуан Гамильтон и придуманная им игра.

* * *