Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Часть 5. Алгоритмы на графах. они предпринимают соответствующие действия, когда сталкиваются различными типами ребер во время поиска в глубину
|
|
они предпринимают соответствующие действия, когда сталкиваются различными типами ребер во время поиска в глубину. Например, рассмотрим следующую фундаментальную задачу. Обнаружение направленного цикла. Существуют ли в заданном орграфе направленные циклы? (Является ли рассматриваемый орграф графом DAG?) В неориентированных графах любое ребро, ведущее в посещенную вершину, означает наличие цикла в таком графе; в орграфе мы должны в этом плане сосредоточить внимание на обратных ребрах.
Программа 19.2. DFS на орграфе_____________________________________________
Данный класс DFS использует нумерацию в прямом и обратном порядке для того, чтобы показать, какую роль играет каждое ребро графа в поиске в глубину (см. рис. 19.10).
template < class Graph> class DFS { const Graph & G;
int depth, cnt, cntP; vector< int> pre, post; void show (char *s, Edge e)
{ for (int i = 0; i < depth; i++) cout «" ";
cout «e.v «" -" «e.w «s «endl; } void dfsR(Edge e)
{ int w = e.w; show(" tree", e); pre[w] = cnt++; depth++; typename Graph:: adjIterator A(G, w); for (int t = A.beg();! A.end(); t = A.nxt()) { Edge x(w, t); if (pre[t] == -1) dfsR(x);
else if (post[t] == -1) show(" back", x); else if (pre[t] > pre[w]) show(" down", x); else show(" cross", x); } post[w] = cntP++; depth--;
} public:
DFS(const Graph & G): G(G), cnt(0), cntP(O), pre(G.V(), -1), post(G.V(), -1) { for (int v = 0; v < G.V(); v++)
if (pre[v] == -1) dfsR(Edge(v, v)); } };
Свойство 19.4. Орграф является графом DAG тогда и только тогда, когда, воспользовавшись алгоритмом поиска в глубину для проверки каждого ребра, мы не сталкиваемся с обратными ребрами.
Доказательство: Любое обратное ребро принадлежит некоторому направленному циклу, который состоит из этого ребра плюс путь в дереве, соединяющий два соответствующих узла, так что мы не найдем ни одного обратного ребра при использовании поиска в глубину на DAG. Чтобы доказать обратное утверждение, мы покажем, что если в орграфе имеется цикл, то поиск в глубину выходит на обратное ребро. Предположим, что v есть первая из вершин цикла, на которую выходит поиск в глубину. Эта вершина имеет наименьший номер в прямом порядке обхода всех вершин цикла. В силу этого обстоятельства, ребро, которое ведет в нее, будет обратным ребром: на него мы выйдем во время рекурсивного вызова для вершины v (доказательство того, что мы таки на него обязательно выйдем, приводится в свойстве 19.5), при этом оно указывает из одного из узлов цикла на v, т.е. на узел с меньшим номером в обратном порядке (см. свойство 19.3). ■
Глава 19. Орграфы и ориентированные ациклические графы
РИСУНОК 19.11. ЛЕС ПОИСКА В ГЛУБИНУ НА ОРГРАФЕ
Изображенные на рисунке леса описывают поиск DFS (depth first search — поиск в глубину) на том же графе, что и представленный на рис. 19.9, в рамках которого функция поиска на графе проверяет вершины (и вызывает эту рекурсивную функцию для непосещенных вершин) в порядке s, s+i,..., 0, 1,..., s-1 для каждого s. Структура леса определяется как динамикой поиска, так и структурой самого графа. Каждый узел порождает одних и тех же потомков (в порядке следования узлов в его списке смежных вершин) в каждом лесу. Крайнее дерево слева в каждом лесу содержит все вершины, достижимые из его корня, однако проблема достижимости из других вершин усложняется фактом наличия обратных, поперечных и прямых ребер. Даже число деревьев в лесе зависит от выбора начальной вершины, так что совсем не обязательно существование прямого соответствия между деревьями в лесу и сильными компонентами, какое возможно в случае неориентированных графов. Например, мы убеждаемся в том, что все вершины достижимы из вершины 8 только в том случае, когда мы начинаем поиск в глубину из вершины 8.
Часть 5. Алгоритмы на графах
Мы можем преобразовать любой орграф в DAG, выполнив поиск в глубину и удалив любые ребра графа, которые соответствуют обратным ребрам при поиске в глубину. Например, из рис. 19.9 мы видим, что удалив ребра 2-0, 3-5, 2-3, 9-11, 10-12, 4-2 и 7-8, мы получим из орграфа, показанного на рис 19.1, граф DAG. Конкретный граф DAG, который мы получаем подобным способом, зависит от представления преобразуемого графа и от вызванных этим преобразованием последствий для динамических свойств поиска в глубину (см. упражнение 19.37). Этот метод представляет собой способ генерации произвольных графов DAG (см. упражнение 19.76), используемых при тестировании алгоритмов обработки графов DAG.
Обнаружение направленного цикла является простой задачей, однако отличие только что описанного решения от решения, которое рассматривалось в главе 18 для случае неориентированных графов, убеждает нас в необходимости трактовать два этих типа графов как различные комбинаторные объекты, даже если их представления подобны, и одни и те же программы работают на обоих типах в условиях некоторых видов приложений. Согласно нашему определению, возникает впечатление, будто мы используем для решения этой проблемы тот же метод, что и для обнаружения циклов в неориентированных графах (поиск обратных ребер), однако реализация, которой мы воспользовались для неориентированных графов, на орграфе работать не будет. Например, в разделе 18.5 мы очень осторожно подходили к различиям между родительскими связями и обратными связями, поскольку существование родительской связи отнюдь не указывает на наличие цикла (циклы в неориентированных графах должны содержать, по меньшей мере, три вершины). В то же время игнорирование обратных связей, ведущих в орграфах в родительские узлы, некорректно; мы рассматриваем дважды связные пары вершин в орграфах как циклы. Теоретически мы могли бы определить обратные ребра в неориентированных графах так же, как это только что было проделано, однако в таком случае мы должны были бы сделать однозначное исключение для случая с двумя вершинами. И что более важно, мы можем обнаруживать циклы в неориентированных графах за время, пропорциональное V (см. раздел 18.5), однако нам может понадобиться время, пропорциональное Е, чтобы обнаружить цикл в орграфе (см. упражнение 19.32).
Одна из главных целей поиска в глубину заключается в том, чтобы обеспечить систематический способ посещения всех вершин и всех ребер графа. В силу этого обстоятельства он дает нам фундаментальный подход к решению проблемы достижимости в орграфах, хотя опять-таки ситуация намного сложнее, нежели в случае неориентированных графов.
Достижимость из единственного источника. Какие вершины заданного орграфа могут быть достигнуты из заданной начальной вершины s? Сколько таких вершин имеется в заданном графе?
Свойство 19.5. Посредством рекурсивного поиска в глубину, начинающегося в вершине s, мы можем решить задачу достижимости из единого истока для вершины s за время, пропорциональное числу ребер в подграфе, индуцированном достижимыми вершинами.
Доказательство: Доказательство во многом аналогично доказательству свойства 18.1, однако имеет смысл еще раз подчеркнуть различие между достижимостью в орграфах и связностью в неориентированных графах. Это свойство, несомненно, справедливо для орграфа, который состоит из одной вершины и не содержит ребер. Для любого
Глава 19, Орграфы и ориентированные ациклические графы
орграфа, содержащего более одной вершины, предположим, что это свойство справедливо для всех орграфов, состоящего из меньшего числа вершин. Теперь первое ребро, которое мы выберем из вершины s, делит рассматриваемый орграф на два подграфа, индуцированных двумя поднаборами вершин (см. рис 19.12): (i) вершинами, достижимыми через ориентированные пути, которые начинаются с этого ребра и не содержат s в своем дальнейшем протяжении; и (if) вершины, которые мы не можем достичь через какой-либо ориентированный путь, начинающийся с этого ребра, без возврата в s. К этим подграфам мы применяем индуктивное предположение, заключающееся в том, что ориентированные ребра, ведущие в s, будут проигнорированы, поскольку эта вершина имеет меньший номер в прямом порядке, чем любая вершина второго подграфа, так что все ориентированные ребра, исходящие из вершин второго подграфа и ведущие в первый подграф, будут проигнорированы. При этом отмечается факт, что не существует ориентированных ребер, ведущих из одной из вершин первого подграфа в любую отличную от s вершину второго графа (существование такого ребра приводит к противоречию, ибо вершина назначения должна находиться в первом подграфе). ■
В отличие от неориентированных графов, поиск в глубину на орграфе не дает полной информации о достижимости из любого другого узла, отличного от исходного, поскольку ребра дерева являются ориентированными, а поисковые структуры содержат поперечные ребра. Когда мы покидаем какую-либо вершину и отправляемся в обход вниз по дереву, мы не можем быть уверены в том, что существует обратный путь в эту вершину через ребра орграфа; на самом деле такого пути в общем случае не существует. Например, нет такого пути, чтобы вернуться в вершину 4 после выбора ребра дерева 4-11 на рис. 19.9. Более того, если мы игнорируем поперечные и обратные ребра (поскольку они ведут в вершины, которые принимали посещения и больше на могут быть активными), мы игнорируем всю информацию, которую они несут (набор вершин, которые достижимы из вершины назначения отвергнутого ребра). Например, проход на рис. 19.9 вдоль ребра 6-9 представляет собой единственную возможность убедиться в том, что вершины 10, 11 и 12 достижимы из вершины 6.
РИСУНОК 19.12. ДЕКОМПОЗИЦИЯ ОРГРАФА
Доказательство методом индукции того факта, что поиск в глубину приводит нас в любое место, достижимое из заданного узла орграфа, по существу ничем не отличается от исследования Тремо. Основное действие изображено здесь в виде лабиринта (вверху), чтобы можно было провести сравнение с рис. 18.4. Мы разбиваем граф на две части меньших размеров (внизу), прожденные двумя множествами вершин: вершинами, которые могут быть достигнуты, если следовать вдоль первого ребра, исходящего из начальной вершины, без ее повторного посещения (нижняя часть), и теми вершинами, которые остаются недостижимыми, если следовать вдоль первого ребра, не возвращаясь в исходную вершину (верхняя часть). Любое ребро, исходящее из вершины, принадлежащей второму множеству, и ведущее в какую-либо вершину первого множества, пропускается, ибо все вершины первого множества помечены еще до того, как начнется поиск во втором подграфе.