2014-02-12
3316
Вершина w орграфа D достижима из вершины v, если:
а) v = w;
б) существует путь из v в w.
Орграф называется сильно связным, если для любых его вершин v, w существует путь из v в w, и из w в v.
Орграф называется односторонне связным, если для любых двух вершин хотя бы одна достижима из другой.
Пример:
u2
u1 сильно связный граф
u3
u2
u1 односторонне связный граф
u3
Псевдографом, ассоциированным с ориентированным псевдографом D(V, X), называется псевдограф G(V, X0), в котором Х0 получается заменой всех упорядоченных пар (v, w) на неупорядоченные {v, w}.
Пример: Дан орграф D(V, X):
Для него G (V, X0):
Орграф называется слабо связным, если связным является ассоциированный с ним псевдограф.
В рассмотренном выше примере граф G (V, X0) связный, значит орграф D(V, X) – слабо связный.
Если орграф не является слабо связным, то он называется несвязым.
Пример:
Представленный на этом рисунке граф D(V, X) – несвязный, т.к. ассоциированный ему граф G(V, X0) – несвязный, т.к. р(G) = 2.
Компонентой сильной связности графа D называется его сильно связный подграф, не являющийся собственным подграфом никакого другого сильно связного подграфа орграфа D.
|
|
|
Пример:
Этот орграф имеет две компоненты сильной связности:
 | |||
 | |||
D1 D2
Значит Р (D) = 2.
Замечание: Вершина достижима сама для себя, поэтому является сильно связным подграфом.
Орграф D(V, X) Компоненты сильной связности орграфа D(V, X)
Этот граф имеет три компоненты сильной связности.
Из определения компоненты сильной связности следует справедливость утверждений:
Пусть D1(V1, X1) – компонента сильной связности орграфа D(V, X), тогда D1 – подграф орграфа D(V, X), порожденный множеством V1.
Пусть D(V, X) – орграф с р компонентами сильной связности: D1(V1, X1),…, Dр(Vр, Xр). Тогда:
1) V = V1 È…ÈVp, X Í X1 È…È Xp;
2) Vi ÇVj = Æ, Xi ÇXj = Æ, если i ¹ j;
3) n(D1) +…+ n(Dp) = n(D), m(D1) +…+ m(Dp) £ m(D).
