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 к и, то оно становится обратным ребром (когда оно исследуется, вершина и – серая).