Вернемся к задаче Эйлера о кенигсбергских мостах. По существу, задача сводится к построению в графе цикла, который содержит каждую дугу графа по одному разу. Графы, в которых такой цикл существует, образуют важный класс графов.
ОПРЕДЕЛЕНИЕ 27.Цикл в графе называется эйлеровым, если каждая дуга графа входит в него один раз и каждая вершина – хотя бы один раз. Граф называется эйлеровым, если в нем существует эйлеров цикл. Не замкнутый путь в графе называется эйлеровым, если каждая дуга графа входит в него один раз и каждая вершина – хотя бы один раз. Граф называется полуэйлеровым, если в нем существует эйлеров путь.
Легко привести примеры таких графов. Проверка эйлеровости графа очень проста.
Теорема 20. Следующие три утверждения эквивалентны.
1. Граф эйлеров.
2. Граф сильно связный и у каждой вершины полустепени входа и выхода равны.
3. Граф сильно связный и существует семейство простых циклов таких, что каждая дуга графа принадлежит одному из циклов.
Доказательство. Доказывать теорему будем по схеме 1®2®3®1.
1®2. Пусть граф эйлеров. Поскольку все вершины принадлежат эйлерову циклу, то граф сильно связный. Эйлеров цикл в каждую вершину входит столько же раз, сколько выходит. Поскольку при этом проходятся все дуги графа, то условие 2 выполняется.
2®3. Будем строить путь, начиная с произвольной вершины пока какая-нибудь вершина не повторится. Полустепени входа и выхода вершин не меньше единицы – в противном случае граф не был бы сильно связным. Это означает, что построение пути не может прерваться до повторения вершины. Тем самым, образовался простой цикл. Удалим его из графа. Полустепени входа и выхода некоторых вершин уменьшаются на 1, т.е. остаются равными. (Сильно связным оставшийся граф может и не быть.) Продолжая построение, мы получим разбиение множества дуг на несколько простых циклов, что и требовалось.
3®1. Рассмотрим какой-нибудь цикл. Если в него входят все дуги (а тогда в силу сильной связности и все вершины), то граф эйлеров. В противном случае выберем какой-нибудь из имеющихся простых циклов, который имеет с исходным общую вершину. Такой цикл существует, поскольку в противном случае граф не был бы сильно связным. Из этих двух циклов формируется цикл (не простой). Продолжая процесс, получим эйлеров цикл.
Очевидно, аналогичные рассуждения применимы и к неориентированным графам. Основное условие 2 заменяется на связность и четность степеней вершин.
Из теоремы следует, что полуэйлеровость связного неориентированного графа равносильна существованию ровно двух вершин с нечетными степенями.
Таким образом, алгоритм проверки эйлеровости очень прост: надо проверить сильную связность (связность) и подсчитать полустепени входа и выхода (степени) всех вершин.
Обсудим алгоритмы построения эйлеровых циклов. Один такой алгоритм следует из доказательства: надо строить простые циклы так, как описано, затем их «склеивать».
Приведем еще один эффективный алгоритм построения эйлерова цикла в неориентированных графах – алгоритм Форда. Нам потребуется понятие моста. Мостомв графе называется дуга, удаление которой приводит к росту числа компонент. Алгоритм Форда состоит из нескольких правил.
1. Начинать движение из любой вершины.
2. Не двигаться по мостам, если есть другая возможность.
3. Стирать пройденные дуги и изолированные вершины.