Эйлеровы графы

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

Алгоритм построения эйлерова цикла

Предполагается, что граф связен и удовлетворяет условиям Эйлера. Все ребра графа не имеют индексов. Приведем описание алгоритма:

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 _нач последовательным обходом ребер графа. На каждом шаге выбираем ребро с наибольшим индексом. Если таких ребер несколько, то берем любое из них.