Определение путей и контуров Эйлера

 

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

Если серьезно, то поиск путей и контуров Эйлера имеет более практичное применение. Их можно использовать для проложения маршрута по каким-либо реальным сетям таким образом, что каждое ребро будет проходиться в точности один раз. Существуют некоторые свойства, которыми должен обладать граф, чтобы в нем имелся путь или контур Эйлера.

Рис. 4. Граф, который имеет путь Эйлера, и сам этот путь.

 

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

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

Теперь очевидно, что для графа требуются ограничения. Граф не должен быть связанным. Однако этот граф должен содержать только один связанный подграф. Если граф содержит больше одного связанного подграфа, то он не может иметь путей или контуров Эйлера, так как некоторые ребра никогда не будут пройдены.

Любой граф, который удовлетворяет указанным условиям, должен иметь путь Эйлера или контур Эйлера. Такой граф называется эйлеровским.

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

На рисунках 5—8 показан пример выполнения такого алгоритма. Работа алгоритма заключается в локализации циклов в графе с использованием похожей на глубинный поиск методики. Эти циклы затем можно скомбинировать для образования одного цикла, который проходит по всем ребрам в графе, — цикла Эйлера. Алгоритм можно описать как последовательность следующих действий:

1. Инициализировать список циклов.

2. Выполнять глубинный поиск, пока все ребра не будут удалены из графа. Добавить текущий номер вершины в текущий путь. Пройти ребро, образованное в процессе поиска, и удалить его. Если ребер для просмотра больше нет, то добавить текущий путь в список циклов, а затем продолжить поиск непройденных вершин, начиная с первой вершины.

3. Объединить пути и циклы вместе для формирования контура Эйлера.

Рис. 5. Исходный граф.

 

Рассмотрим подробнее этот алгоритм. Глубинный поиск начинается с вершины v0 и на последующих итерациях посещаются вершины v1 и v3. После v3 достигается v0, и полученный цикл считается найденным. Затем цикл v0, v1, v4, v3 и v0 сохраняется.

Рис 6. Ребра графа, по которым проходит

путь 0->1->4->3-> 0 удаляются.

 

Затем глубинный поиск продолжается с первой вершины, которая имела выходящее из нее ребро. В нашем случае это вершина v,. При глубинном поиске может быть найден цикл v1, v2, v5, v4, v4, v7, v6, v3, v1 который добавляется в список циклов. Рис. 7 демонстрирует граф без второго найденного цикла.

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

Рис. 7. Граф с удаленными ребрами

по пути 1->2->5->4->7->6->3->1.

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

Рис. 8. Найденный контур Эйлера.

 

Эффективная реализация этого алгоритма может оказаться немного громоздкой. Потенциальную проблему представляют неориентированные графы из-за обычного способа их представления. Хотя в графе ребро является единственным объектом, оно представляется как два ориентированных ребра, одно из которых идет от u к v, а другое — от v к u.

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

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