Учебное пособие C#. Алгоритмы и структуры данных н. А. Тюкачев, В. Г. Хлебостроев издание третье, стереотипное 1 / 23

5.5.1. Э
ЙЛЕРОВЫ ЦИКЛЫ
 
Цикл, проходящий через все ребра графа, называется эйлеровым цик-
лом.
Теорема Эйлера 
Связный неориентированный граф содержит эйлеров цикл тогда и 
только тогда, когда число его вершин, имеющих нечетную степень, равно 0 
или 2. 
Эта теорема была доказана Эйлером в 1736 г. считается первой в тео-
рии графов. На рисунке 5.13 представлен эйлеров путь для неориентирован-
ного графа из девяти узлов. 
Рис. 5.13. Эйлеров путь 
Рассмотрим алгоритм построения эйлерова пути. Для реализации алго-
ритма потребуется два стека: рабочий стек myStack и стек для эйлерова пу-
ти path. Алгоритм содержит следующие шаги.
16 / 23

---

178 
1.
Очистить признаки посещения узлов. 
2.
Выбрать в качестве исходного любой узел, например, узел с 
номером v = 0; поместить номер этого узла в стек myStack. 
3.
Если этот стек не пуст, то для текущего узла найти ребро, со-
единяющее его со смежным непосещенным узлом. Если стек 
пуст, то завершить выполнение алгоритма. 
4.
Если такое ребро найдено то, поместить в стек myStack но-
мер соответствующего смежного узла, пометить ребро как 
пройденное и перейти на шаг 3. Если ребро не найдено, то 
выполнить шаг 5. 
5.
Извлечь номер узла из стека myStack, т. е. вернуться назад, 
поместить номер узла в стек пути path и перейти на шаг 3. 
Результат работы алгоритма накапливается в стеке path. Два метода, 
совместно реализующих алгоритм построения эйлерова пути, представлены в 
листинге 5.35. 
Листинг 5.35. Эйлеровы пути 
int FindEdge(int v) 
{ 
int LL = 0; 
if (Nodes[v].Edge != null) 
{ 
LL = Nodes[v].Edge.Length; 
bool Ok = false; int i = -1; 
while ((i < LL - 1) && !Ok) 
Ok = Nodes[v].Edge[++i].color != 
Color.Black; 
if (Ok) return i; else return -1; 
} 
else 
return -1; 
} 
public void PathEuler() 
{ 
ClearVisit(); 
17 / 23

---

179 
Lib.myStack = new MyStack(); 
Lib.path = new MyStack(); 
int v = 0; 
Lib.myStack.Push(v); // 
положить в стек 
while (!Lib.myStack.isEmpty()) 
{ 
int i = FindEdge(v); 
if (i != -1) 
{ 
int u = Nodes[v].Edge[i].numNode; 
Lib.myStack.Push(u); // 
положить в стек 
SetEdgeBlack(v, i); // 
закрасить ребра 
v = u; 
} 
else 
{ 
v = (int)Lib.myStack.Pop(); 
// 
взять из стека 
Lib.path.Push(v); // 
положить в стек 
} 
} 
}