Клауди Альсина - Том 11. Карты метро и нейронные сети. Теория графов

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

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

* * *

ЭЙЛЕРОВЫ ЦИКЛЫ В ЗАНИМАТЕЛЬНЫХ ЗАДАЧАХ

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

* * *

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

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

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

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

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

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

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

* * *

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

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

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

* * *

МЕТОД ПОСТРОЕНИЯ ДЕРЕВА

На рисунках ниже показано, как можно сопоставить исходному графу ABCDдерево всех возможных маршрутов для поиска гамильтоновых циклов, которые начинаются и заканчиваются в вершине А, а вершины В, Си Dобходятся ровно один раз. С увеличением числа вершин поиск гамильтоновых циклов усложняется: в каждом случае исходным является полный граф с nвершинами (им соответствует nгородов). Из каждого города можно попасть в n — 1 город, из каждого из них — в n— 2 города и так далее, пока мы не вернемся в начальную точку. Следовательно, число маршрутов будет равно ( n— 1)·( n— 2)·( n— 3)·… ·3·2·1. Вспомним, что факториалом числа называется произведение всех натуральных чисел от 1 до этого числа включительно (например, 6! = 6·5·4·3·2·1), следовательно, общее число циклов будет равно ( n— 1)!. Так как каждый цикл можно пройти в прямом и обратном направлении, то общее число различных циклов будет в два раза меньше: ( n-1)1/2. Впрочем, и это число будет очень велико: для n— 6 оно составит (6–1)!/2 = 60 циклов.

* * *

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