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

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

В дальнейшем количество компонент связности графа будем обозначать k.

Пример 79.

Данный граф не является связным: k = 3.

Данный граф является связным: k = 0.

У графа, изображенного на рис.3.18, три компоненты связности. У орграфа, изображенного на рис.3.19, три компоненты сильной связности, показанные на рис.3.20.

Рис. 3.18

Рис. 3.19 Рис. 3.20

Так же, как в неориентированном случае, понятие связности приводит к понятию связной компоненты: подграф орграфа называется связной компонентой орграфа , если:

1) является связным орграфом;

2) не существует связного орграфа такого, что и .

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

Компонентой связности называется максимальный связный подграф графа G (V, E). Число компонент связности графа обозначается k (G).

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

Если для любых двух вершин u и v графа G (V, ) существует маршрут из u в v или из v в u, то граф называется связным или односторонне связным.

Теорема. Пусть G – простой граф с n вершинами и k компонентами. Тогда число m его ребер удовлетворяет неравенствам

Следствие. Любой простой граф с n вершинами и более чем (т-1)(т-2)/2 ребрами связен.

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

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

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

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

Определение. Разрезом называется такое разделяющее множество, никакое собственное подмножество которого не является разделяющим.

Определение. Разрез, состоящий из одного ребра, называется мостом (перешейком).

Пример 80.

Для графа, изображенного на рис.33, каждое из множеств {e1, e2, e5} и {e3, e6, e7, e8} является разделяющим.

Разрезом является множество ребер {e1, e2}.

В графе возможно выделить несколько разделяющих множеств и разрезов.

 

Утверждение. Пусть G1(V1, X1) – компонента связности (сильной связности) графа (орграфа) G. Тогда G1 – подграф графа (орграфа) G, порожденный множеством V1.

Данное утверждение справедливо и для произвольных ориентированных и неориентированных псевдографов.