1.7.Эйлеровы пути

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

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

Eiler = proc (g:graph; v:int) returns (CE:stack)

effects 1. T = stack.new; CE = stack.new

2.stack.pop(T,v)

3. пока not(stack.isempty (T))

3.1.v = stack.top (T)

3.2.c = graph.fetch (g,v); если (circ.size (c) <> 0), то

3.2.1. u = circ.element (c)

3.2.2.stack.pop (T,u)

3.2.3.circ.delete (c) / удаление u из структуры с

3.2.4.c = graph.fetch(g,u); пока (circ.elenent (c) <> v) circ.change (c);

circ.delete (c) / удаление v из структуры с

3.2.5.v = u

иначе

3.2.6.v = stack.push (T)

3.27.stack.pop (CE,v)

Рис.1.24.Процедура нахождения эйлерова цикла в графе, начиная с вершины v.

На рис.1.25 представлен граф и некоторый эйлеров цикл, найденный алгоритмом Eiler.

Не менее важное значение фундаментальное множество циклов играет в геометрическом моделировании многогранных объектов, представленных планарными графами (рис.1.1). Каждый фундаментальный цикл в этом графе будет соответствовать дескриптору грани объекта, выраженному через вершины F(S). То есть, имея исходную геометрическую модель в виде S(S), с помощью отыскиваемого алгоритма можно реализовать преобразование S(S) в F(S).