Выделение связных(сильных компонент) в орграфах. Построение конденсации

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

Конденсация графа - представление исходного графа в виде конденсированного, в котором каждая вершина соответствует сильно связной компоненте исходного графа.

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

Для примера рассмотрим орграф на рис.1.17а и составим для него часть множеств (рис.1.17б) и матрицу достижимостей (рис.1.17в).

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

Граф (орграф) называется связным (сильно связным), если для любых , существует маршрут (путь) из в .

Односторонне связным называется орграф, если для любых , существует путь из в или из в .

Орграф называется слабо связным, если связным является ассоциированный с ним неориентированный граф. Если граф (орграф) не является связным (слабо связным), то он называется несвязным.

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

Очевидно, что элементы СК определяются множеством . Пусть . Найдем очередную СК , так чтобы . Получим множество вершин новой СК . Продолжим процесс выделения СК до тех пор пока они иссякнут. Тогда сформируем граф такой, что есть выделенные СК, а дуга существует в тогда и только тогда, когда в существует дуга такая, что , а , причем такая, что . Полученный таким образом граф называется конденсацией. На рис.1.18б представлены все СК графа на рис.1.18а, а конденсация представлена на рис.1.18в

Если положить, что для графа построена матрица достижимости , то можно предложить эффективный метод выделения всех СК и построения конденсации.

Для этого введем матрицу , где символ обозначает кронекерово или прямое произведение матриц, при котором элементы матрицы () определяются соотношением . Тогда для элементов матрицы справедливо: .

Поскольку все вершины достижимы и контрдостижимы для себя же (), то . Если же для это значит, что и , а следовательно вершина достижима из , а вершина достижима из а следовательно они взаимодостижимы и входят в одну СК.

Так для графа на рис.1.18 матрицы и имеют вид

.

Тогда алгоритм выделения СК и построения конденсации может иметь следующий вид: (далее – множество вершин конденсации, – множество задействованных уже в СК вершин, - текущая СК, -текущее число СК в графе.

Шаг 1. Установка начальных значений: .

Шаг 2. Контроль для выхода: Если идти в конец, (шаг 4), иначе к шагу 3.

Шаг 3. Выделение СК: Полагаем . Для , , формируем , , . Переходим к шагу 2.

Шаг 4. Окончание.

, .

Для графа 1.18 в результате работы алгоритма получим таблицу:

Для матрицы смежности размером 3х3 получим отличные от нуля элементы:

, т.к. существует дуга, например , такая, что и ;

,т.к. существует дуга, например , такая, что и ;

,т.к. существует дуга, например , такая, что и .

Остальные элементы равны нулю. Тогда ,

что и отражено на рисунке 1.18.б и 1.18в.

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