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

Вершина w орграфа D достижима из вершины v, если:

а) v = w ;

б) существует путь из v в w.

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

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

Пример:

u₂

u₁ сильно связный граф

u₃

u₂

u₁ односторонне связный граф

u₃

Псевдографом, ассоциированным с ориентированным псевдографом D(V, X), называется псевдограф G(V, X₀), в котором Х₀ получается заменой всех упорядоченных пар (v, w) на неупорядоченные {v, w}.

Пример: Дан орграф D(V, X):

Для него G (V, X₀):

Орграф называется слабо связным, если связным является ассоциированный с ним псевдограф.

В рассмотренном выше примере граф G (V, X₀) связный, значит орграф D(V, X) – слабо связный.

Если орграф не является слабо связным, то он называется несвязым.

Пример:

Представленный на этом рисунке граф D(V , X) – несвязный, т.к. ассоциированный ему граф G(V, X₀) – несвязный, т.к. р(G) = 2.

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

Пример:

Этот орграф имеет две компоненты сильной связности:

D₁ D₂

Значит Р (D) = 2.

Замечание: Вершина достижима сама для себя, поэтому является сильно связным подграфом.

Орграф D(V , X) Компоненты сильной связности орграфа D(V , X)

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

Из определения компоненты сильной связности следует справедливость утверждений:

Пусть D₁(V₁, X₁) – компонента сильной связности орграфа D(V, X), тогда D₁ – подграф орграфа D(V, X) , порожденный множеством V₁.

Пусть D(V, X) – орграф с р компонентами сильной связности: D₁(V₁, X₁) ,…, D_р(V_р, X_р) . Тогда:

1. V = V₁ …V_p , X  X₁ … X_p ;

2. V_i V_j = , X_i X_j = , если i  j ;

3. n(D₁) +…+ n(D_p) = n(D), m(D₁) +…+ m(D_p)  m(D).