Компонента сильной связности в орграфе

Сильно связными компонентами орграфа называются его максимальные по включению сильно связные подграфы.

Алгоритм построения глубинного остовного леса:

Шаг 1. Выбираем в Gпроизвольную вершину u₁, которая образует подграф G_iлеса G, являющийся деревом.

Шаг 2. Если i= n, где n= n(G) (проверка на наличие всех вершин исходного леса в построенном остовном лесу), то задача решена, и G_i, искомый остовныйлеслесаG. В противном случае переходим к шагу 3.

Шаг 3. Пусть уже построено дерево G_i, являющееся подграфом лесаG и содержащее некоторые вершины u₁, ...u_i, где 1<i<n-1. Строим граф G_i+1, добавляя к деревуG_iновую вершину u_i+1, смежную в Gс некоторой вершиной u_j графа G_i, и новое ребро {u_i+1 , u_j}.Если такое ребро есть, то присваиваем i:=i+l и переходим к шагу 2. Если невозможно найти ребро, соединяющее вершину u_i+1с вершиной u_j (в силу возможной несвязности леса G), то переходим к шагу 4.

Шаг 4.Принимаем вершину u_j+1из шага 3 за начало нового дерева в лесу G, присваиваем i:=i+l и переходим к шагу 2.

Классификация ребер оргафа

1. Ребра деревьев—это ребра, входящие в лес поиска в глубину. На рис. 2 это ребра (1, 2), (2, 3), (2, 5), (3, 4).

2. Обратные ребра—это ребра, соединяющие вершину с ее предкомв дереве поиска в глубину (ребра-циклы, возможные в ориентированных графах, считаютсяобратнымиребрами).Нарис. 2 эторебра (5, 1), (6, 6).

3. Прямые ребра—это ребра, соединяющие вершину с ее потомком, но не входящие в лес поиска в глубину: (2, 4) на рис. 2.

4. Перекрестные ребра—все остальные ребра графа.Онимогут соединять две вершины из одного дерева поиска в глубину, если ниодна их этих вершин не является предком другой, или же вершины из разных деревьев: (5, 4), (6, 1) на рис. 2.