Свойства поиска в глубину

 

Прежде всего отметим, что подграф предшествования (составленный из
деревьев поиска в глубину) в точности соответствует структуре рекурсивных
вызовов процедуры DFS-VISIT. Именно, u = [v] тогда и только тогда, когда
произошёл вызов DFS-VISIT(v) во время просмотра списка смежных с и вершин.

Другое важное свойство состоит в том, что времена обнаружения и окон-
чания обработки образуют правильную скобочную структуру (parenthesis struc-
ture). Будем обозначать обнаружение вершины и открывающейся скобкой с пометкой и, а окончание её обработки закрывающейся с тои же пометкой.
Тогда перечень событий будет правильно построенным выражением из скобок
(парные скобки имеют одинаковые пометки). Например, поиску в глубину на
рис. 5.3(а) соответствует расстановка скобок, изображённая на рис. 5.3(б).

Чтобы доказать эти и другие свойства, мы должны рассуждать по индук-
ции. При этом, доказывая требуемое свойство рекурсивной процедуры DFS--
VISIT, мы предполагаем, что рекурсивные вызовы этой процедуры обладают
выбранным свойством.

Убедимся вначале, что вызов DFS-VISIT(u) для белой вершины и делает
чёрной эту вершину и все белые вершины, доступные из неё по белым путям
(в которых все промежуточные вершины также белые), и оставляет серые и
чёрные вершины без изменений.

В самом деле, рекурсивные вызовы в строке 6 выполняются лишь для белых
вершин, являющихся смежными с и. Если какая-то вершина w была закрашена
в ходе этих вызовов, то (по индуктивному предположению) она была доступна
по белому пути из одной из белых вершин, смежных с и, и потому доступна по
белому пути из и.

Напротив, если вершина w доступна по белому пути из и, то она доступна
по белому пути из какой-то белой вершины v, смежной с и (посмотрим на
первый шаг пути). Будем считать, что v первая из таких вершин (в порядке
просмотра в строке 3). В этом случае все вершины белого пути из v в w
останутся белыми к моменту вызова DFS-VISIT(v), поскольку они недоступны по
белым путям из предшествующих vвершин (иначе w была бы также доступна).
По индуктивному предположению w станет чёрной после вызова DFS-VISIT(v).

Кроме того, сама вершина и станет сначала серой, а потом чёрной. (За-
метим, что мы могли бы сразу сделать её чёрной, и программа осталась бы
правильной, так как она никак не различает серые и чёрные вершины, однако
различие между серым и чёрным нам пригодится в дальнейшем.)

 

Рисунок 5.3 – Свойства поиска в глубину

На рис. 5.3 изображены: (а) Результат поиска. (б) Промежутки между обнаружением и окончанием обработки для каждой из
вершин, изображённые в виде прямоугольников. Стрелки указывают структуру деревьев
поиска в глубину. (в) Отмечены рёбра исходного графа с указанием их типов (рёбра дерева
и прямые рёбра ведут вниз, обратные ведут вверх).

Ясно также, что цвета серых и чёрных вершин остаются без изменений
(поскольку это верно для рекурсивных вызовов по индуктивному предположе-
нию).

Аналогичные рассуждения по индукции позволяют установить, что вызов
DFS‑VISIT(u) меняет поля [v] для всех окрашиваемых вершин v, отличных
от и, тем самым формируя из них дерево с корнем в и, а также добавляет
кописанному выше протоколу из скобок с пометками правильное скобочное
выражение, внешние скобки которого имеют пометку и, а внутри находятся
скобки с пометками, соответствующими окрашиваемым вершинам.

Подводя итоги, можно сформулировать следующие утверждения.

 

Теорема 5.2 (о скобочной структуре).При поиске в глубину в ориентирован-
ном или неориентированном графе G = (V, Е) для любых двух вершин u и v
выполняется ровно одно из следующих трёх утверждений:

 

• отрезки [d[u], f [u]] и [d[v], f[v]] не пересекаются;
• отрезок [d[u],f[u]] целиком содержится внутри отрезка [d[v],f[v]] и u – потомок v в дереве поиска в глубину;
• отрезок [d[v], f[v]] целиком содержится внутри отрезка [d[u], f[u]] и v –
  потомок и в дереве поиска в глубину.

 

Следствие 5.3 (вложение интервалов для потомков). Вершина v является (от-
личным от u) потомком вершины и в лесе поиска в глубину для (ориентирован-
ного или неориентированного) графа G, если и только если d[u] < d[v] < f [v] <
f[u].

Теорема 5.4 (о белом пути). Вершина v является потомком вершины u в лесе
поиска в глубину (для ориентированного или неориентированного графа G =
(V, Е)) в том и только том случае, если в момент времени d[u], когда
вершина u обнаружена, существует путь из u в v, состоящий только из
белых вершин.

5.2.7 Классификация рёбер

 

Рёбра графа делятся на несколько категорий в зависимости от их роли
при поиске в глубину. Эта классификация оказывается полезной в различных
задачах. Например, как мы увидим в следующем разделе, ориентированный граф
не имеет циклов тогда и только тогда, когда поиск в глубину не находит в нём
«обратных» ребер.

Итак, пусть мы провели поиск в глубину на графе G и получили лес .

 

1. Рёбра деревьев (tree edges) это рёбра графа . (Ребро (и, v)будет ребром дерева, если вершина v была обнаружена при обработке этого ребра.)

2. Обратные рёбра (back edges) – это рёбра (и, v), соединяющие вершину и с её предком v в дереве поиска в глубину. (Рёбра-циклы, возможные в ориентированных графах, считаются обратными рёбрами.)

3. Прямые рёбра (forward edges) соединяют вершину с её потомком, но не входят в дерево поиска в глубину.

4. Перекрёстные рёбра (cross edges) – все остальные рёбра графа. Они могут соединять две вершины одного дерева поиска в глубину, если ни одна из этих вершин не является предком другой, или же вершины из разных деревьев.

 

На рисунках 5.2 и 5.3 рёбра помечены в соответствии со своим типом.
Рис. 5.3(в) показывает граф рис. 5.3(а), нарисованный так, чтобы прямые
рёбра и рёбра деревьев вели вниз, а обратные вверх.

Алгоритм DFS может быть дополнен классификацией рёбер по их типам.
Идея здесь в том, что тип ребра (и, v) можно определить по цвету вершины v
в тот момент, когда ребро первый раз исследуется (правда, прямые и пере-
крёстные ребра при этом не различаются): белый цвет означает ребро дерева,
серый – обратное ребро, чёрный – прямое или перекрёстное ребро.

Чтобы убедиться в этом, надо заметить, что к моменту вызова DFS-
-VISIT(u) серыми являются вершины на пути от корня дерева к вершине и и
только они (индукция по глубине вложенности вызова). Чтобы отличить прямые
рёбра от перекрёстных, можно воспользоваться полем d: ребро (u, v) оказывается
прямым, если d[u] < d[v], и перекрёстным, если d[u] > d[v].

Неориентированный граф требует особого рассмотрения, так как одно и
то же ребро (и, v) = (v, u) обрабатывается дважды, с двух концов, и может попасть вразные категории. Мы будем относить его к той категории, которая
стоит раньше в нашем перечне четырёх категорий. Тот же самый результат
получится, если мы будем считать, что тип ребра определяется при его первой
обработке и не меняется при второй.

Оказывается, что при таких соглашениях прямых и перекрёстных рёбер в
неориентированном графе не будет.

Теорема 5.5. При поиске в глубину в неориентированном графе G любое ребро оказывается либо ребром дерева, либо обратным.

Доказательство. Пусть (и, v)произвольное ребро графа G, и пусть, напри-
мер, d[u] < d[v]. Тогда вершина v должна быть обнаружена и обработана прежде,
чем закончится обработка вершины и, так как и содержится в списке смежных
с и вершин. Если ребро (и, v) первый раз обрабатывается в направлении от u
к v, то (и, v) становится ребром дерева. Если же оно первый раз обрабатыва-
ется в направлении от v к и, то оно становится обратным ребром (когда оно
исследуется, вершина и – серая).