5.10. Связность в ориентированных графах

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

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

В ориентированных графах различают несколько понятий связности.

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

Ориентированный граф G(V, X) называется односторонне-связным, если для любой пары вершин , существует путь либо из в , либо из в .

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

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

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

Для нахождения сильно связных подграфов введем понятие матрицы достижимости , элементы которой равны 1, если вершина достижима из , или равны 0 в случае отсутствия пути из в .

Матрица контрдостижимости (матрица обратных достижимостей) , определяется следующим образом: элементы равны 1, если вершина достижима из , или равны 0 в случае отсутствия пути из в . Матрица контрдостижимости может быть получена из матрицы достижимости с помощью транспонирования, т.е. .

Матрица взаимодостижимости имеет элементы , которые равны 1, если вершины и одновременно достижимы друг для друга, или равны 0 в случае отсутствия пути из в или из в . Матрица взаимодостижимости может быть получена из матриц достижимости и контрдостижимости с помощью почленного перемножения по правилу

.

Отношение взаимодостижимости разбивает все множество вершин V орграфа G на сильно связные компоненты.

Для орграфа, изображенного на рис. 25, матрица достижимости R, контрдостижимости Q и взаимодостижимости H представлены ниже.

Матрица достижимости R и контрдостижимости Q и взаимодостижимости H орграфа, изображенного на рис. 24 , имеют вид:

, , .

Анализируя матрицу взаимодостижимости, находим следующие классы взаимодостижимых вершин (бикомпоненты): {v₁,v₂,v₃,v₄}, {v₅,v₆}, которые представлены на рис.24 справа.

Е сли каждой компоненте сильной связности графа поставить в соответствие некоторую вершину. Дуги между этими вершинами будут существовать в новом графе G* тогда и только тогда, когда в исходном графе G существует дуга , такая, что принадлежит компоненте, соответствующей вершине x_i*, а – компоненте, соответствующей вершине x_j*. В этом случае получится граф G* называют конденсацией графа G. На рис. 26 изображен граф G и его конденсация G*.