Связность. Компоненты связности

Пусть дан псевдограф G(V,X).

Две вершины v и w называются связанными (или вершина v достижима из w), если :

а) v = w;

б) существует маршрут, связывающий вершины v и w.

Определенное на множестве V отношение достижимости или связности является бинарным эквивалентным отношением (проверьте самостоятельно). А значит, множество V можно разбить на классы эквивалентности V₁ V₂ …V_k, где V₁ V₂ …V_k=V и V₁ V₂ …V_k = .

Все вершины, принадлежащие одному подмножеству Vi связанные, а вершины, принадлежащие разным подмножествам – несвязанные.

Каждое подмножество Vi называется компонентой связности графа G(V,X).

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

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

Количество компонент связности графа G(V,X) обозначается P(G).

На рисунке 13.9 представлен граф, у которого три компоненты связности, т.е. P(G) =3: G₁, G₂, G₃

G₁ G₂ G3

Рис. 13.9.

Введем понятие связного графа.

Граф G(V,X) называется связным, если любые две его вершины достижимы (связанные).

Или: граф G(V,X) называется связным, если P(G) = 1.

Тогда, несвязный граф имеет P(G) >1.

С понятием компонента связности связаны понятия: разделительная вершина (точка сочленения) и мост.

Введем еще одну операцию над графом – удаление вершины.

Операцией удаления вершины называется удаление некоторой вершины вместе с инцидентными ей ребрами.

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

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

Для графа 13.5 найдем все разделительные вершины и мосты:

разделительные вершины: v₂, v₄,

мост : {v₁, v₂}.