Понятия эйлеров граф, эйлеров цикл и эйлерова цепь были рассмотрены выше. Рассмотрим алгоритмы построения эйлерового цикла и эйлеровой цепи, и их применение для нахождения покрытия графа непересекающимися по ребрам цепями.
Алгоритм построения эйлерова цикла
Предполагается, что граф связен и удовлетворяет условиям Эйлера. Все ребра графа не имеют индексов. Приведем описание алгоритма:
1) Положить i = 1. Построить простой цикл с началом в некоторой вершине w (в первый раз это будет вершина v нач).
2) Всем ребрам построенного цикла присвоить индекс i. Если ребер без индекса больше нет, то к п. 4, иначе к п. 3.
3) Положить i = i + 1, среди ребер без индекса выбрать ребро, смежное одному из ребер с индексом. Построить простой цикл из еще не помеченных ребер, содержащий выбранное ребро, и перейти к п. 2.
4) Строим эйлеров цикл с началом в v нач последовательным обходом ребер графа. На каждом шаге выбираем ребро с наибольшим индексом. Если таких ребер несколько, то берем любое из них.
Алгоритм построения эйлеровой цепи
Если требуется построить эйлерову цепь, то:
1) Сначала строится простая цепь между вершинами с нечетными степенями. ее ребрам присваиваются индексы i = 1.
2) Если ребер без индекса больше нет, то к п. 4, иначе к п. 3.
3) Положить i = i + 1, среди ребер без индекса выбрать ребро, смежное одному из ребер с индексом. Построить простой цикл из еще не помеченных ребер, содержащий выбранное ребро, присвоить ребрам этого цикла индекс i и перейти к п. 2.
4) Строим эйлеров цикл с началом в v нач последовательным обходом ребер графа. На каждом шаге выбираем ребро с наибольшим индексом. Если таких ребер несколько, то берем любое из них.