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

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

Теорема 23.6 (о скобочной структуре).

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

отрезки/[и]] и [[и],/[и]] не пересекаются;

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

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

Следствие 23.7 (вложение интервалов для потомков)

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

Теорема 23.8 (о белом пути)

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

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

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

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

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

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

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

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

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

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

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

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

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

Теорема 23.9

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

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

Эта теорема будет не раз использована в следующих разделах.

Упражнения.

23.3-1

Нарисуйте таблицу 3x3, строки и столбцы которой отмечены как БЕЛЫЙ, СЕРЫЙ и ЧЁРНЫЙ. В каждой клеткепометьте,

Рис. 23.5 23.6 Ориентированный граф для упр. 23.3-2 и 23.3-3.

может ли в процессе поиска в глубину на ориентированном графе найтись ребро из вершины цвета г в вершину цвета j, и какого типа может быть такое ребро. Сделайте аналогичную таблицу для неориентированных графов. 23.3-2

Примените алгоритм поиска в глубину для графа рис. 23.6. Считайте, что цикл for в строках 5-7 процедуры DFS перебирает вершины в алфавитном порядке, и что в списках смежных вершин они тоже идут по алфавиту. Найдите время обнаружения и окончания обработки каждой вершины. Укажите типы всех ребер.

23.3-3

Напишите выражение из скобок, соответствующее поиску в глубину в предыдущем упражнении. 23.3-4

Докажите, что ребро (и, v) является

a.ребром дерева или прямым ребром, если и только если d[u] < d[v] < f[v] < f[u];

b.обратным ребром, если и только если d[v] < d[u] < f[u] < f[v];

c.перекрёстным ребром, если и только если d[v] < f[v] < d[u] <

/М-

23.3-5

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

23.3-6

Постройте контрпример к такой гипотезе: если в ориентированном графе G существует путь из и в v, и если d[u] < d[v] при поиске в глубину на этом графе, то v - потомок и в построенном лесу поиска в глубину.

23.3-7

Модифицируйте алгоритм поиска в глубину так, чтобы он печатал каждое ребро ориентированного графа вместе с его типом. Какие изменения нужны для неориентированного графа?

23.3-8

Объясните, как вершина может оказаться единственной в дереве поиска в глубину, даже если у неё есть как входящие, так и исходящие ребра.

23.3-9

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