Связность в графах

Орграф называется сильносвязанным, если для любых двух вершин V_i и V_j найдется путь из Vi в Vj, и наоборот путь из Vj в Vi. В противном случае граф называется несвязным.

На рис. 2 показаны сильносвязный и несильносвязный графы.

V3

V2

V1

Рис.2

Компонентой сильной связности орграфа G называется его подграф G`, удовлетворяющий следующим условиям:

1) подграф G` - сильносвязный;

2) добавление к G` любой вершины Vi из графа G c дугами инцидентности V нарушает условие сильной связности подграфа G`.

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

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

Прямым транзитивным замыканием вершины Vi орграфа называется выражение

где - множество вершин графа, в которые ведут дуги из вершины Vi;

- множество вершин графа, в которые ведут дуги из множества вершин ;

- множество вершин графа, в которые ведут дуги из множества вершин , т.д.

Таким образом, - это множество вершин графа, в которые ведут пути из Vi, включая и вершину Vi, или множество вершин графа, достижимых из Vi.

Обратным транзитивным замыканием вершины Vi орграфа называется выражение

где - множество вершин графа, из которых идут дуги в вершину Vi и т.д.

Если для вершины Vi найдены и , то компонента сильной связности, включая вершину Vi,может быть найдена так:

.

1.3.1 Алгоритм нахождения компонент сильной связности (алгоритм Мальгранжа-Томеску)

1) Граф задается матрицей смежности (рис.3).

			…

2) Матрица смежности дополняется столбцом и строкой , где Vi выбирается крайним слева среди столбцов. Переходят к алгоритму заполнения столбца.

3) Если столбец заполнен, переходят к алгоритму заполнения строки .

Алгоритм заполнения строки аналогичен алгоритму заполнения столбца.

4) Находят

5) В матрице смежности вычеркиваются все строки и столбцы, соответствующие вершинам, входящим в найденную компоненту сильной связности . Алгоритм повторяется до тех пор, пока не будут вычеркнуты все строки и столбцы матрицы смежности.

1.3.2 Алгоритм заполнения столбца .

1) В клетке столбца , являющейся продолжением строки Vi матрицы смежности, ставится нуль. Переход к п.2.

2) Если в клетках матрицы смежности на пересечении i-ой строки и столбцов Vj,…,Vk стоят единицы, то в клетках столбца , являющихся продолжением строк Vj,…,Vk ставятся единицы. Переход к п.3.

3) Если в клетках матрицы смежности на пересечении строк Vj,…,Vk со столбцами Vp,…,Vm стоят единицы, то в клетках столбца являющихся продолжением строк Vj,…,Vk ставится цифра 2. Переход к п.4.

4) Процесс заполнения столбца продолжается до тех пор, пока возможно. Переход к п.5.

5) Если заполнение столбца окончено (не все клетки столбца могут содержать цифры), то выписываются множество вершин графа, соответствующих заполненным клеткам столбца .Это и будет прямое транзитивное замыкание.

Пример

Задана матрица смежности графа. Найти разложение графа на компоненты сильной связности.

На рис.4 показана матрица смежности графа и заполнение столбца и строки , которым соответствует прямое и обратное транзитивное замыкание: ={1,2,3,4,5}, ={1,2,3} и компонента сильной связности ={1,2,3}. После вычеркивания столбцов и строк матрицы смежности с номерами 1,2,3, вошедшими в , рассматривается остаток матрицы, столбец и строка заполняются. В результате получается прямое и обратное транзитивное замыкание и компонента сильной связности: ={4,5}, ={4,5}, ={4,5}.

x

x

x

x

				x	X	x	x
						x	x

Рис.4

Рассмотрение элементов матрицы, оставшихся после вычеркивания столбцов и строк с номерами 4 и 5 дает такие результаты: ={6,7}, ={6,7}, ={6,7}.

Таким образом, представленный граф имеет 3 компоненты сильной связности: , , .