Глава 17, Свойства и типы графов. Программа 17.18. Существование эйлерова цикла

Программа 17.18. Существование эйлерова цикла

Имея в своем распоряжении этот класс, клиентские программы могут проверить существование эйлерова цикла в графе. Вершины v и w рассматриваются как приватные элементы данных, благодаря чему клиентские программы могут воспользоваться функцией-элементом show (которая использует приватную функцию-элемент tour) для печати пути (см. программу 17.19).

В основу этого теста, использующего программу 17.11, положено следствие свойства 17.4. На его выполнение затрачивается время, пропорциональное V, причем сюда не входит время, затрачиваемое на предварительную обработку, в рамках которой производится проверка связности и построение таблицы степеней вершин в классе DEGREE.

template < class Graph> class ePATH { Graph G; int v, w; bool found; STACK < int> S; int tour (int v); public:

ePATH (const Graph & G, int v, int w): G(G), v(v), w(w) { DEGREE< Graph> deg(G);

int t = deg[v] + deg[w];

if ((t % 2)! = 0) { found = false; return; } for (t = 0; t < G.V(); t++) if ((t! = v) & & (t! = w)) if ((deg[t] % 2)! = 0)

{ found = false; return; } found = true; }

bool exists() const { return found; } void show();

};

Программа 17.19. Поиск эйлерова пути с линейным временем выполнения_______

Данная реализация функции show для класса из программы 17.18 выводит на печать эйлеров путь между двумя заданными вершинами, если таковой имеется. В отличие от других наших реализаций, в основу рассматриваемого программного кода положена реализация АТД Graph, в которой имеется соответствующий конструктор копирования, поскольку он строит копию графа и уничтожает эту копию, удаляя ребра из графа во время печати этого пути. При условии, что реализация функции remove выполняется за постоянное время (см. упражнение 17.46), функция show выполняется за линейное время. Приватная функция-элемент tour проходит по ребрам, удаляет их из цикла и помещает вершины в стек, чтобы выявить наличие боковых циклов (см. рассуждения по тексту раздела). Главный цикл продолжает вызывать функцию tour до тех пор, пока существуют боковые циклы.

template < class 6raph> int ePATH< Graph>:: tour(int v) { while (true)

{ typename Graph:: adjIterator A(G, v);

int w = A.beg(); if (A.end()) break; S.push(v);

Часть 5. Алгоритмы на графах

G.remove(Edge(v, w)); v = w; }

return v; }

template < class 6raph> void ePATH< Graph>:: show() {

if (! found) return;

while (tour(v) == v & &! S.empty ())

{ v = S.pop(); cout «" -" «v; } cout «endl; }

Свойство 17.5. Мы можем обнаружить в графе эйлеров цикл, если таковой существует, за линейное время.

Полное доказательство этого свойства методом индукции мы оставляем на самостоя­тельную проработку (см. упражнение 17.100). По существу, после первого вызова фун­кции path в стеке содержится путь от v до w, и оставшаяся часть графа (после удале­ния изолированных вершин) состоит из связных компонент меньших размеров (имеющих, по меньшей мере, одну общую вершину с найденным на текущий момент путем), которые также содержат эйлеровы циклы. Мы выталкиваем изолированные вершины из стека и применяем функцию path для поиска тем же способом эйлеровых циклов, которые содержат неизолированные вершины. Каждое ребро графа заталки­вается в стек (и выталкивается из него) в точности один раз, в силу чего общее вре­мя выполнения пропорционально Е. ■

Несмотря на то что эйлеровы циклы допускают систематический обход всех ребер и вершин, мы довольно редко используем их на практике в силу того обстоятельства, что лишь немногие графы содержат такие циклы. Вместо этого для исследования графов мы обычно применяем метод поиска в глубину, который подробно рассматривается в главе 18. В самом деле, как мы убедимся позже, поиск в глубину на неориентированном гра­фе эквивалентен вычислению двухпроходного эйлерова цикла (two way Euler tour) — пути, который проходит по каждому ребру в точности два раза, по одному в каждом направ­лении.

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

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