SearchR(G, 0, 6) 0-1 searchR(G, 1, 6) 1-0 1-2 0-2

SearchR(G, 5, 6) 5-0

SearchR(G, 4, 6) 4-2

SearchR(G, 3, 6) 3-2 3-4 4-6 searchR(G, 6, 6)

РИСУНОК 17.17. ТРАССИРОВКА ПОИСКА ПРОСТОГО ПУТИ

Данная трассировка показывает, как работает рекурсивная функция из программы 17.16 на примере вызова searchR(G, 2, 6) с целью поиска простого пути из вершины 2 в вершину б на графе, который показан в верхней части рисунка. Для каждого исследуемого ребра в трассе отводится отдельная строка с отступом на один уровень для каждого рекурсивного вызова. Чтобы проверить ребро 2-0, мы осуществля­ем вызов searchR(G, 0, 6). Этот вызов заставляет нас проверить ребра 0-1, 0-2 и 0-5. Чтобы прове­рить ребро 0-1, мы делаем вызов searchR(G, 1, 6), который заставля­ет нас проверить ребра 1-0 и 1-2, которые не приводят к рекурсивным вызовам, поскольку вершины 0 и 2 уже помечены. В этом примере рассматриваемая функция обнару­живает путь 2-0-5-4-6.

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

Мы проведем подробные исследования алгоритма по­иска в глубину в его более общей формулировке в сле­дующем разделе, там же мы рассмотрим несколько дру­гих алгоритмов связности. Например, несколько более общая версия программы 17.16 предлагает нам способ обхода всех ребер графа путем построения вектора, ин­дексированного именами вершин, который позволяет клиенту проверить за постоянное время, существует ли путь, соединяющий какие-либо две вершины.

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

Гамильтонов путь. Пусть даны две вершины, суще­ствует ли простой путь, соединяющий эти вершины, ко­торый проходит через каждую вершину графа в точное-

РИСУНОК 17.18. ГАМИЛЬТОНОВ ПУТЬ

В графе, помещенном в верхней части рисунка, имеется гамиль­тонов путь 0-6-4-2-1-3-5-0, который заходит в каждую вершину в точности один раз и возвращается в ту вершину, в которой он начинался; в то же время, граф в нижней части рисунка такого пути не содер­жит.

Глава 17, Свойства и типы графов

bool searchR (int v, int w, int d) {

if (V == w) return (d == 0); visited [v] = true;

typename Graph:: adjIterator A(G, v); for (int t = A.beg();! A.end(); t = A.nxt()) if (! visited[t])

if (searchR(t, w, d-l)) return true; visited[v] = false; return false/ }

Свойство 17.3. Рекурсивный поиск гамильтонова цикла может потребовать экспоненциального времени.

Доказательство: Рассмотрим граф, у которого вершина V-1 изолирована, а ребра, связывающие остальные V — 1 вер­шин, образуют полный граф. Программа 17.17 никогда не найдет гамильтонова пути, в то же время, применив метод индукции, легко убедиться в том, что она исследует все (V— 1)! путей в полном графе, каждый из которых требу­ет V— 1 рекурсивных вызовов. Следовательно, общее чис­ло рекурсивных вызовов равно V! или примерно (V/e)^v, что больше, чем любая константа в V-той степени. ■

Полученные нами реализации - программа 17.16, осуще­ствляющая поиск простых путей, и программа 17.17, выполня­ющая поиск гамильтоновых путей, - очень похожи друг на друга. Если таких путей не существует, выполнение обеих программ прекращается, когда всем элементам вектора visited установлено значение true. Почему времена прогона этих про­грамм столь разительно отличаются друг от друга? Прогон программы 17.16 гарантированно выполняется за короткое время, поскольку она устанавливает, по меньшей мере, один элемент вектора visited в 1 всякий раз, когда вызывается фун­кция searchR. С другой стороны, программа 17.17 может ус­танавливать элементы вектора visited снова в 0, так что мы не можем гарантировать, что ее выполнение завершится скоро.

Выполняя поиск простых путей с помощью программы 17.16, мы знаем, что если существует путь из v в w, мы найдем его, выбирая одно из ребер v-t, исходящее из v; то же можно сказать и о гамильтоновых путях. Но на этом сходство закан­чивается. Если мы не можем найти простой путь из t в w, то приходим к выводу, что простого пути из v в w, проходящего через t, не существует; однако такая ситуация в процессе по­иска гамильтонова пути не возникает. Может случиться так, что в графе нет гамильтонова пути в вершину w, который на­чинается с ребра v-t, но есть путь, который начинается с v-x-t и проходит через вершину х. Мы должны выполнять рекур-

РИСУНОК 17.19. ТРАССИРОВКА ПОИСКА ГАМИЛЬТОНОВА ПУТИ

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

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

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

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

Эйлеров путь. Существует ли путь, соединяющий две заданных вершины, который проходит через каждое реб­ро графа в точности один раз? Путь не обязательно дол­жен быть простым — вершины можно посещать много­кратно. Если путь начинается из некоторой вершины и возвращается в ту же вершину, мы имеем задачу поиска эйлерова цикла (Euler tour). Существует ли циклический путь, который проходит через каждое ребро графа в точ­ности один раз? В следствии к свойству 17.4 мы докажем, что задача поиска такого пути эквивалентна задаче поис­ка цикла в графе, построенного путем добавления в граф ребра, соединяющего две соответствующие вершины. На рис. 17.20 приводятся два небольших примера.

Первым эту классическую задачу исследовал Л.Эйлер (L.Euler) в 1736 г. Некоторые математики склонны счи­тать, что начало исследованию графов и теории графов

РИСУНОК 17.20. ПРИМЕРЫ ЭЙЛЕРОВЫХ ЦИКЛОВ И ЦЕПЕЙ

Граф, показанный в верхней части рисунка, содержит эйлеров цикл 0-1-2-0-6-4-3-2-5-0, который использует все ребра в точности один раз. Граф, изображенный в нижней части рисунка, не содержит таких циклов, однако содержит эйлеров путь 0-2-0-1-3-4-2-3-5-4-6-0-5.