![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Глава 17, Свойства и типы графов. Программа 17.18. Существование эйлерова цикла
В основу этого теста, использующего программу 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(); };
Данная реализация функции 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. Алгоритмы на графах
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.100). По существу, после первого вызова функции path в стеке содержится путь от v до w, и оставшаяся часть графа (после удаления изолированных вершин) состоит из связных компонент меньших размеров (имеющих, по меньшей мере, одну общую вершину с найденным на текущий момент путем), которые также содержат эйлеровы циклы. Мы выталкиваем изолированные вершины из стека и применяем функцию path для поиска тем же способом эйлеровых циклов, которые содержат неизолированные вершины. Каждое ребро графа заталкивается в стек (и выталкивается из него) в точности один раз, в силу чего общее время выполнения пропорционально Е. ■ Несмотря на то что эйлеровы циклы допускают систематический обход всех ребер и вершин, мы довольно редко используем их на практике в силу того обстоятельства, что лишь немногие графы содержат такие циклы. Вместо этого для исследования графов мы обычно применяем метод поиска в глубину, который подробно рассматривается в главе 18. В самом деле, как мы убедимся позже, поиск в глубину на неориентированном графе эквивалентен вычислению двухпроходного эйлерова цикла (two way Euler tour) — пути, который проходит по каждому ребру в точности два раза, по одному в каждом направлении. Подводя итог сказанному в этом разделе, отметим, что поиск простых путей в графах не представляет трудностей, что еще легче определить, сможем ли мы обойти через все ребра крупного графа, не проходя ни по одному из них дважды (достаточно всего лишь убедиться в том, что степени всех вершин суть четные числа), и что даже существует " умный" алгоритм, способный найти такой цикл, но в то же время практически невозможно узнать, можем ли мы обойти все вершины графа, не посетив ни одну из них дважды. В нашем распоряжении имеются рекурсивные решения всех этих задач, однако высокая вероятность экспоненциального возрастания времени выполнения делает эти решения практически бесполезными. Другие решения позволяют получить быстродействующие алгоритмы, удобные для практического применения. Такой разброс похожих на первый взгляд задач по трудности решения, иллюстрацией которого могут послужить эти примеры, характерен для обработки графов и является фундаментальным свойством в теории вычислений. Из краткого анализа, проводимого в
|