Связность графа и компоненты связности

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

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

° ° °

° ° ° ° ° °

° ° ° ° ° °

а б в

Рис. 2.

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

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

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

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

Понятие сильной компоненты иллюстрирует рис. 3.

° ° ° ° ° °

° ° ° °

° ° ° ° ° °

° ° ° ° ° °

° ° °

° ° ° ° °

Рис. 3

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

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

Графы являются связными и в сумме дают граф . Эти графы называются компонентами связности графа . Число – еще одна числовая характеристика графа. Для связного графа , если граф несвязный, то .

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