Алгоритм Флери.

1. Произвольно выбирают некоторую вершину v₁ и ребро u₁, инцидентное v₁. Этому ребру присваивают номер 1. Вычеркивают это ребро u₁ и переходят в вершину v₂ по ребру .

2. Находясь в вершине v_i , не следует выбирать ребро, соединяющее v_i c v₁ , если имеется возможность иного выбора; не следует выбирать ребро, которое является перешейком (т.е. ребром, при удалении которого граф, образованный не вычеркнутыми ребрами, распадается на две компоненты связности, каждая из которых имеет хотя бы по одному ребру).

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

Пример. Построить эйлеров цикл в графе G , изображенном на рис. 5. 1.

□ Граф G эйлеров, так как , и граф связный.

1. Выберем v₁ и ребро и присвоим ему номер 1, затем перейдем в вершину v_i = v₇ .

2. Находясь в v₇, не выбираем вычеркнутое ребро 1. Из оставшихся трех

Рис. 5.1

ребер ни одно не является перешейком, поэтому выбираем любое, например, , присваиваем ему номер 2 и переходим в вершину v_i = v₆ .

3. После восьми шагов опять приходим в вершину v₁ . Построенный цикл :

Но построенный цикл не охватывает все ребра графа (рис. 5.1). Для выполнения этого условия можно было взять ребро , присвоить ему номер 2 и перейти в вершину v_i = v₂ . Дальнейший обход графа показан на рисунке

■

Аналогично алгоритм Флери используется для построения эйлерова контура. Орграф должен быть сильно связным. Иначе можно не вернуться в начальную вершину.

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