5.2.7 Классификация рёбер
Рёбра графа делятся на несколько категорий в зависимости от их роли при поиске в глубину. Эта классификация оказывается полезной в различных задачах. Например, как мы увидим в следующем разделе, ориентированный граф не имеет циклов тогда и только тогда, когда поиск в глубину не находит в нём «обратных» ребер.
Итак,
пусть
мы
провели
поиск
в
глубину
на
графе
G
и
получили
лес
.
Рёбра деревьев (tree edges) это рёбра графа
.
(Ребро
(и, v)
будет
ребром
дерева,
если
вершина
v
была
обнаружена
при
обработке
этого
ребра.)Обратные рёбра (back edges) – это рёбра (и, v), соединяющие вершину и с её предком v в дереве поиска в глубину. (Рёбра-циклы, возможные в ориентированных графах, считаются обратными рёбрами.)
Прямые рёбра (forward edges) соединяют вершину с её потомком, но не входят в дерево поиска в глубину.
Перекрёстные рёбра (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 к и, то оно становится обратным ребром (когда оно исследуется, вершина и – серая).