Методы программирования

Задание 8. Поиск двусвязных компонент и точек сочленения

Общая информация

Задание обязательно для желающих получить оценку «отлично».

Теория

Компонентой связности неориентированного графа будем называть любой максимальный связный подграф этого графа. Это определение можно переформулировать так: компонента связности — это такой подграф, что для любой вершины u из этого подграфа все вершины, в которые в исходном графе существует путь из u, принадлежат этому же подграфу. На рисунке изображен граф, имеющий две компоненты связности.

Будем называть некоторую вершину неориентированного графа точкой сочленения, если при удалении ее и всех инцидентных ей ребер в графе увеличивается количество компонент связности. Эквивалентным определением является следующее: вершина u является точкой сочленения тогда и только тогда, когда в графе существуют две вершины v и w, отличные от u и принадлежащие одной компоненте связности, такие, что любой путь из v в w проходит через u.

Будем называть граф двусвязным, если он не содержит точек сочленения. Всякий максимальный двусвязный подграф графа будем называть двусвязной компонентой. Другими словами, двусвязная компонента графа — это любой его подграф, в котором удаление произвольной вершины и инцидентных ей ребер не влечет потерю связности этого подграфа, и к этому подграфу нельзя добавить ни одной вершины, сохранив это свойство. На рисунке в графе выделены точки сочленения (вершины 2 и 4) и указаны двусвязные компоненты ({1, 2, 4}, {4, 6, 7}, {2, 3}, {5, 8}).

Заметим, что любые две различные двусвязные компоненты либо не имеют общих вершин, либо имеют одну общую вершину, которая является точкой сочленения.

Сформулируем без доказательства следующую теорему.

Теорема. Пусть D — остовное дерево (каркас) неориентированного связного графа G, построенный методом поиска в глубину от вершины r. Вершина v является точкой сочленения графа G тогда и только тогда, когда:

Изменим процедуру обхода графа в глубину, добавив в нее вычисление двух массивов: int number[N] и int L[N], где N — количество вершин графа. Для каждой вершины v в number[v] будем хранить номер этой вершины в порядке обхода графа в глубину, а в L[v] запишем число number[w], где w — вершина, которая связана обратным ребром с v или каким-либо из потомков v в остовном дереве и имеет минимальный возможный номер number, либо number[v], если такой вершины w найти не удалось. Напомним, что обратными ребрами мы называем ребра, не вошедшие в каркас графа, построенный обходом в глубину.

Разберем подробнее смысл значений L[v]. На рисунке построено остовное дерево графа с корнем в вершине r = 1 и выписаны значения массивов number[N] и L[N]. Для корня остовного дерева L[r] = used[r] = 1. Для вершины 2 значение L[2] равно 1, т.к. из вершины 4 (потомка вершины 2 в остовном дереве) можно вернуться по обратному ребру в вершину 1, для которой number[1] = 1. Аналогично, значения L[6] и L[7] равны 4, потому что из вершины 7 (потомка вершины 6) можно вернуться по обратному ребру в вершину, номер number которой равен четырем.

Зная значения L и number, найти точки сочленения не составляет труда. Согласно приведенной выше теореме, вершина, не являющаяся корнем остовного дерева, будет являться точкой сочленения тогда и только тогда, когда для какого-либо из ее потомков в остовном дереве значение L будет больше либо равно значению number самой вершины. Это означает, что из этого потомка невозможно найти обратное ребро, соединенное с предком рассматриваемой вершины, и по теореме вершина будет являться точкой сочленения. Случай с корнем рассматривается отдельно: корень является точкой сочленения тогда и только тогда, когда у него существует больше одного сына в остовном дереве.

Сформулируем алгоритм поиска точек сочленения более строго. Реализуем рекурсивную функцию void go(int curr, int prev), где curr — текущая вершина, а prev — вершина, из которой мы попали в текущую. При первом вызове curr = r, prev = –1. В теле функции будут выполняться следующие шаги:

Данный алгоритм заполнит массивы L[N] и number[N] требуемым образом. Проверять, является ли вершина точкой сочленения, можно на шаге 3a. Также, если реализовать стек для хранения ребер, можно реализовать вывод самих двусвязных компонент: ребро нужно добавлять в стек на шагах 3a (перед рекурсивным вызовом) и 3b и выталкивать из стека в поток вывода все ребра вплоть до текущего (curr, i), если на шаге 3а выяснилось, что для текущей вершины curr выполняется условие теоремы.

Формулировка задания

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