Поиск точек раздела, мостов и двусвязных компонент
Определения
Пусть задан неориентированный связный граф
G = (V, E).
Вершина
u называется
точкой раздела графа
G, если после удаления этой вершины граф распадается на две или более компоненты связности. Под удалением вершины понимается переход к подграфу
G', индуцированному множеством вершин
V \ {u}, или, другими словами, удаление вершины и всех исходящих из нее ребер.
Аналогично, ребро
e называется
мостом графа, если после удаления этого ребра граф распадается на две или более компоненты связности.
Далее, определим на множестве ребер
E следующее отношение
R: скажем, что пара различных ребер
e1 и
e2 удовлетворяет отношению
R, если в графе существует простой цикл, содержащий оба эти ребра. Также по определению положим, что каждое ребро
e связано отношением
R с самим собой. Покажем, что
R является отношением эквивалентности. Действительно,
R рефлексивно по определению (
e = e (mod R)). Симметричность
R очевидна. Докажем, что
R транзитивно. Пусть пары ребер
(e1, e2) и
(e2, e3) удовлетворяют
R. Для ребер
e1,
e2 существует простой цикл
C, содержащий оба эти ребра:
Рисунок 1
Обозначим
p и
q концы ребра
e2 (на рисунке не показаны),
u и
v концы ребра
e3. Тогда существуют простые непересекающиеся по вершинам пути
p -> u и
q -> v (возможно, после перемены мест обозначений
p и
q). Обозначим за
x последнюю вершину на пути
p -> u, принадлежащую циклу
C. Аналогично за
y обозначим последню вершину пути
q -> v, принадлежащую
C. Заметим, что
x и
y различны, поскольку принадлежат двум путям, не имеющим общих вершин. Значит, пара вершин
x и
y разбивает цикл
C на две части. В одной из этих частей находится ребро
e1 = (a, b) Значит, ребра
e1 и
e3 содержатся в цикле
x -> a -> b -> y -> v -> u -> x. Очевидно, что указанный цикл является простым, следовательно ребра
e1 и e3 также связаны отношением R.
Итак, мы доказали, что указанное отношение
R удовлетворяет всем свойствам отношения эквивалентности. Следовательно, множество всех ребер
E можно разбить на классы эквивалентности относительно
R. Те из этих классов, что содержат хотя бы два ребра, называются
двусвязными компонентами графа
G.
Идеи алгоритмов
Здесь не будет приводиться описания алгоритмов такого подробного, как, скажем, псевдокод. Вместо этого будут доказаны утверждения, на которых основываются алгоритмы поиска. Конкретные детали и собственно реализацию поиска можно найти в коде на C++, ссылки на который приведены в конце страницы.
Все определенные объекты (мосты, точки раздела и двусвязные компоненты) можно найти при помощи поиска в глубину. Выполним в графе поиск в глубину, начиная из некоторой вершины
r (root). Поскольку граф связен, граф поиска в глубину
Gp является деревом с корнем в
r. Как известно, в неориентированном графе все ребра либо принадлежат
Gp, либо являются
обратными. При поиске сохраним в массивах
enter[] и
leave[] время начала и конца обработки каждой вершины. Определим дополнительно числовую функцию
low на множестве вершин следующим образом: рассмотрим в дереве
Gp поддерево с корнем в
u. За
low[u] положим минимальное значение
enter[v], где
v пробегает множество концов всех обратных ребер с началом в этом поддереве, а также саму вершину
u.
Точки раздела
Утверждение 1. Корень дерева поиска
r является точкой раздела тогда и только тогда, когда в этом дереве у него есть хотя бы две дочерних вершины. Действительно, если у
r только одна дочерняя вершина, то после удаления
r любая вершина будет по-прежнему достижима из любой по ребрам дерева
Gp. Если же у
r есть хотя бы две дочерних вершины
x и
y, то после удаления
r вершины поддерева с корнем
x будут недостижимы из вершин поддерева с корнем
y (как уже упоминалось, при обходе в глубину неориентированного графа могут быть обратные ребра, но не может быть прямых и перекрестных).
Утверждение 2. Вершина
u, отличная от
r, является точкой раздела тогда и только тогда, когда хотя бы для одной из ее дочерних вершин
v выполнено неравенство
low[v] >=
enter[u].
Доказательство. Переформулируем утверждение: вершина
u не является точкой раздела тогда и только тогда, когда для любой ее дочерней вершины
v выполнено
low[v] < enter[u]. Обозначим за
W множество всех вершин, не входящих в поддерево с корнем
u. Пусть
v[1], ...,
v[k] - дочерние вершины
u. За
T1, ..., Tk обозначим поддеревья с корнями в этих вершинах. Между вершинами из этих поддеревьев нет ребер (перекрестные ребра отсутствуют). Граф
G сохранит связность после удаления
u тогда и только тогда, когда из каждого поддерева
Ti будет вести хотя бы одно ребро в
W. Поскольку ребра
Gp Ti с
W соединять не могут, это могут быть только обратные ребра, то есть ребра, ведущие к одному из предков вершины
u. Вполне очевидно, что
enter[v] > enter[u] для любой вершины
v из
Ti и
enter[v] < enter[u] для всякого предка
v вершины
u. Значит, из поддерева
Ti ведет хотя бы одно ребро в
W тогда и только тогда, когда
low[v[i]] < enter[u], что и требовалось.
Теперь, если известны значения функций
enter и
low, пользуясь утверждениями 1 и 2 можно без труда найти точки раздела.
Мосты
Для поиска мостов и двусвязных компонент приведем еще несколько утверждений.
Утверждение 3. Ребро
e является мостом тогда и только тогда, когда оно не содержится ни в одном простом цикле. Действительно, если ребро принадлежит простому циклу, то его концы достижимы друг из друга даже после удаления этого ребра, следовательно удаление такого ребра не может привести к распаду на несколько компонент связности. И наоборот, если при удалении ребра
(a, b) граф остается связным, то существует простой путь из
a в
b, не содержащий
(a, b). Добавив ребро
(b, a) к этому пути, получим простой цикл, что и требовалось.
Следствие 1. Каждый класс эквивалентности относительно отношения
R, введенного выше, является либо двусвязной компонентой, либо состоит из одного моста.
Следствие 2. Никакое обратное ребро
e (при поиске в глубину) не является мостом. Это следует из того, что всякое обратное ребро содержится в каком-либо простом цикле.
Теперь нужно определить, когда прямое ребро
(u, v) является мостом (Здесь
v - дочерняя вершина
u в дереве
Gp). При удалении ребра
(u, v) граф либо останется связен, либо распадется на две компоненты, одна из которых индуцирована вершинами поддерева с корнем в
v. Очевидно, второй случай реализуется если и только если из этого поддерева не ведет обратных ребер в
u или ее предков. Иначе говоря, ребро
(u, v) не является мостом, если
low[v] <=
enter[u], и является, если
low[v] >=
enter[v].
Учитывая все сказанное, при известных функциях
low и
enter не представляет труда отыскать в графе все мосты.
Двусвязные компоненты
Теперь покажем, каким образом найти двусвязные компоненты. Во-первых, если имеется обратное ребро
(u, v), где
v является потомком
u, то оно эквивалентно (везде в этом тексте - в смысле отношения
R) ребру
(v, parents[v]), где parents[v] - родитель вершины
v. Следовательно, достаточно определить, каким двусвязным компонентам принадлежат ребра дерева поиска
Gp, и для обратных ребер принадлежность компонентам тоже будет определена. Ключевым для поиска двусвязных компонент является следующее
Утверждение 4. Пусть
W - множество всех ребер дерева
Gp, принадлежащих некоторой двусвязной компоненте. Тогда
W индуцирует в
Gp связный подграф.
Доказательство. Обозначим рассматриваемую двусвязную компоненту
K. Пусть ребра дерева
Gp e1 и
e2 принадлежат
K. Нужно доказать, что в
Gp существует путь от ребра
e1 к ребру
e2, все ребра которого принадлежат
K. Поскольку
e1 эквивалентно
e2, во всем графе
G существует путь
p, состоящий из ребер компоненты
K, соединяющий
e1 и
e2. Если в этом пути есть обратное ребро
(v, u), где
v - потомок
u, то его можно заменить на путь
v -> parents[v] -> parents[parents[v]] -> ... ->u. Этот путь вместе с ребром
(u, v) образует цикл, следовательно все его ребра эквивалентны
(u, v), то есть лежат в той же двусвязной компоненте
K. Заменив так все обратные ребра пути
p на цепочки из ребер дерева, получим путь, ведущий от ребра
e1 к ребру
e2, состоящий из ребер
K, что и требовалось.
Пусть теперь в дереве
Gp имеется два ребра
e1 и
e2. Нам нужно определить, эквивалентны ли эти ребра (нахождение двусвязных компонент по сути означает умение определить, эквивалентны ли два произвольных ребра). Возьмем в дереве простой путь, начинающийся с ребра
e1 и заканчивающийся ребром
e2. По доказанному утверждению, если ребра
e1 и
e2 эквивалентны, то и вообще все ребра этого пути должны быть эквивалентны между собой. В частности, каждое ребро должно быть эквивалентно следующему за ним ребру. И наоборот, если каждое ребро пути от
e1 до
e2 эквивалентно следующему, то
e1 и
e2 эквивалентны. Следовательно, нам достаточно научиться определять, эквивалентны ли два "соседних" ребра, то есть два ребра, имеющих общую вершину. Возможны два случая, показанные на следующем рисунке.
Рисунок 2.
В первом случае ребра идут от вершины
u к ее родителю
p и дочерней вершине
v (ребра находятся "одно под другим"). Если из поддерева
W с корнем в
v идет обратное ребро в вершину
p или в одного из ее предков, то очевидным образом имеем простой цикл, содержащий
e1 и
e2. И наоборот, если такой цикл существует, то существует простой путь из
v в
p, не проходящий через
u. В какой-то момент этот путь выходит за пределы поддерева
W, следовательно из
W идет обратное ребро в предка
v, причем не в
u, то есть в
p или в ее предка. Итого, в первом случае ребра эквивалентны тогда и только тогда, когда low[v] < enter[u].
Во втором случае ребра идут от вершины
u к двум ее дочерним вершинам
v и
w (ребра находятся "рядом"). Если ребра
e1 и
e2 эквивалентны, то существует простой путь, ведущий из
v в
w, не проходящий по
u. Первое ребро этого пути, выходящее из поддерева
X, является обратным, и ведет в какого-то предка
u (из этого автоматически следует, что вершина
u не может быть корневой). Но тогда ребро
e1 эквивалентно ребру
e, а значит и
e2 ему эквивалентно. Обратно, если
e1 и
e2 оба эквивалентны ребру
e, то они в силу транзитивности
R эквивалентны и между собой. Итак, ребра
e1 и
e2 эквивалентны тогда и только тогда, когда вершина
u не корневая и оба эти ребра эквивалентны ребру
e, идущему от
u к ее родителю. Таким образом, при написании программы можно второй случай никак специально не учитывать: если учтены все эквивалентные пары ребер, соответствующие случаю 1, и алгоритм доопределяет отношение
R по транзитивности, то автоматически будут учтены и пары, соответствующие случаю 2.
Если значения функций
low и
enter известны, то поиском в глубину можно классифицировать ребра (присвоить им идентификаторы, уникальные в пределах двусвязных компонент, построить списки ребер в каждой компоненте, или иным способом определить разбиение множества
E на классы).
Ссылки
--
DanielShved - 26 Mar 2008
no2.draw 
no2.gif 
