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

На первом из следующих рисунков вы можете видеть эйлеров цикл. Во втором графе эйлерова цикла не существует.

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

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

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

* * *

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

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

* * *

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

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

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

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

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

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