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

Подграф G ’ орграфа G (V, E) называется максимальным сильно связным, если не существует сильно связного подграфа G ”, строго содержащего G ’.

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

Вершины компонент сильной связности образуют множество классов эквивалентности C, | C | = p так, что

Принадлежность вершины x_i классу C x_i определяется наличием маршрутов (x_i, x_j) и (x_j, x_i) для любой пары вершин.

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

Определим транзитивное замыканиев графе для вершины x_i

где – множество вершин графа, достижимых из x_i за один шаг,

– множество вершин графа, достижимых из x_i за два шага и т. д.

– это не что иное, как объединение вершины x_i со множеством ее потомков.

Определим обратное транзитивное замыкание в графе для вершины x_i

где – множество вершин графа, из которых x_i достижима за один шаг, – множество вершин графа, из которых x_i достижима за два шага и т.д. – это не что иное, как объединение вершины x_i со множеством ее предков.

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

Поэтому для компонент сильной связности справедливо

где Cx_i – класс эквивалентности.

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

Формальными признаками наличия таких вершин являются:

1) для источников – отсутствие 1 в столбце матрицы смежности,

2) для тупиковых вершин – отсутствие 1 в строке матрицы смежности,

3) для изолированных вершин – отсутствие 1 как в строке, так и в столбце матрицы смежности.

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

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

Алгоритм определения компонент сильной связности орграфа:

1) Удалить из графа вершины источники, тупиковые и изолированные вершины, зафиксировав их как отдельные сильные компоненты.

2) Выбрать некоторую вершину x_i.

3) Определить для x_i .

4) Выполнить операцию пересечения и зафиксировать множество вершин, вошедших в .

5) Удалить из графа вершины, принадлежащие и инцидентные им дуги. Если получен подграф G ’, то перейти к п. 2. Если граф пуст, то перейти к п. 6.

6) Сформировать множество классов C.

Для определения получим степени строки x_i матрицы смежности A, а для определения степени столбца x_i. Максимальный показатель степени n –1, так как учитываются только кратчайшие маршруты. Затем объединим полученные строки (степени строки x_i) со строкой, имеющей единственную 1 в позиции вершины x_i, а полученные столбцы (степени столбца x_i) объединим со столбцом, имеющим единственную 1 в позиции вершины x_i.