Модифицированный алгоритм построения эйлерова цикла

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

циклы, которые мы пытаемся построить, назовем основными. Циклы, которые возникают при некоторых вершинах в процессе построения основных, назовем частными.

Введем две переменные i и j. В i будем подсчитывать общее количество циклов, в j число частных циклов, появляющихся при построении одного основного цикла.

Приведет описание алгоритма:

1) Полагаем i = 1 и j = 1.

2) Случайным блужданием из ребер без индексов строим основной цикл с началом в некоторой вершине w (в первый раз это будет вершина v _нач).

3) Если в процессе построения основного цикла возникает частный цикл при какой–либо вершине, то ребрам этого цикла присваиваем индексы in = i + j и полагаем j = j + 1.

4) Продолжаем строить начатый основной цикл. Если частный цикл не образуется, то к п. 5, иначе к п. 3.

5) После завершения строительства основного цикла, т.е. когда мы вернемся в вершину w, его ребрам присвоим индексы in = i и изменим значения i и j: i = i + j, j = 1.

6) Если ребер без индекса больше нет, то к п. 8, иначе к п. 7.

7) Среди оставшихся ребер без индексов выбираем ребро, инцидентное одной из вершин ранее построенного цикла (построенных циклов), пусть это будет вершина w, и к п. 2.

8) Строим эйлеров цикл с началом в v _нач последовательным обходом ребер графа. На каждом шаге выбираем ребро с наибольшим индексом. Если таких ребер несколько, то берем любое из них.

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