Материал: Дискретная математика. учебное пособие. Горбунов В.В., Лапшина М.Л

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*.

5.11. Эйлеровы графы

Эйлеровой цепью для неориентированного графа называется такая цепь, которая содержит все рёбра графа и притом только по одному разу. Цепь называется эйлеровой, если она содержит все ребра графа.

Эйлеров цикл — это эйлерова цепь, являющийся циклом. Цикл называется эйлеровым, если он содержит все ребра графа.

Эйлеров граф — граф, содержащий эйлеров цикл.

Полуэйлеров граф — граф, содержащий эйлерову цепь.

Теорема Эйлера. Связанный неориентированный граф G содержит эйлеров цикл тогда и только тогда, когда число вершин нечётной степени равно нулю.

Теорема. Граф является полуэйлеровым, если в нем не более двух вершин нечетной степени.

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

Пример 5.2. Граф на рис.27 является эйлеровым, так как в нем есть эйлеров цикл 6123143546.

Пример 5.3. Граф G (рис. 28) является полуэйлеровым, так как цепь 6,1,2,3,1,4,3,5,4,6,5 – эйлерова. В графе G ровно две вершины нечетной степени: v₅ и v₆, поэтому эйлеров цикл отсутствует.

Поиск эйлерова цикла может быть произведен по алгоритму Флери, который состоит в следующем:

1. начинаем с любой вершины и “стираем” пройденные ребра.

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

Пример 5.4. Рассмотрим граф, изображенный на рис. 29 (он эйлеров в силу теоремы Эйлера о циклах) и найдем в нем эйлеров цикл.

Пусть вершина v₁ выбрана как начальная, а ребро (v₁,v₅) стерто на первом шаге. Далее стерто ребро (v₅,v₂) и (v₂,v₆). Тогда текущим графом становится граф, изображенный на рис. 28 справа (текущая вершина v₆). На следующей итерации нельзя выбрать ребро(v₆,v₃) из-за ограничения; вместо него выбрано ребро (v₆,v₅). Дальнейший выбор ребер определен однозначно, так что в итоге будет построен следующий эйлеров цикл: 1,5,2,6,5,4,6,3,2,1.

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

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

Следствие: семейство ребер эйлерова графа можно разбить на непересекающиеся по ребрам циклы.

Теорема. Связный граф является эйлеровым тогда и только тогда, когда его рёбра можно разбить на непересекающиеся простые циклы.

Пример 5.5. Разобьем граф, изображенный на рис. 30, на непересекающиеся простые циклы.

Выберем любую вершину и найдем произвольный цикл. Начнем обход по этому циклу, пока не встретим вершину, одновременно принадлежащую новому циклу. Перескочим на новый цикл. Если при обходе по нему опять встретится вершина, принадлежащая дополнительно еще одному новому циклу, то нужно перескочить на последний новый цикл. Так будет продолжаться, пока не закончатся появляющиеся новые циклы. После обхода последнего цикла произойдет возвращение на предпоследний новый цикл и т.д. В результате вернемся в исходную вершину. В примере получится эйлеров цикл: 1,2,5,4,3,2,4,6,5,1,7,6,1.