Отношение связности, компоненты связности

Случай неориентированного графа

Определение:

Две вершины [math]u[/math] и [math]v[/math] называются связанными (англ. adjacent), если в графе [math]G[/math] существует путь из [math]u[/math] в [math]v[/math] (обозначение: [math]u \rightsquigarrow v [/math]).

Теорема:

Связность — отношение эквивалентности (англ. equivalence relation).

Доказательство:

[math]\triangleright[/math]

Рефлексивность: [math]\forall a \in V a \rightsquigarrow a[/math] (очевидно). Симметричность: [math]a\rightsquigarrow b \Rightarrow b\rightsquigarrow a[/math] (в силу неориентированности графа). Транзитивность: [math]a\rightsquigarrow b \land b\rightsquigarrow c \Rightarrow a\rightsquigarrow c[/math]. Действительно, сначала пройдем от [math]a[/math] до [math]b[/math], затем от [math]b[/math] до [math]c[/math], что и означает существования пути [math]a \rightsquigarrow c[/math].

[math]\triangleleft[/math]

Определение:

Компонентой связности (англ. connected component) называется класс эквивалентности относительно связности.

Определение:

Граф [math]G=(V, E)[/math] называется связным (англ. connectivity graph), если он состоит из одной компоненты связности. В противном случае граф называется несвязным.

Случай ориентированного графа

В общем случае для ориентированного графа существование пути — не симметричное отношение, поэтому вместо понятия связности различают понятие слабой и сильной связности.

Слабая связность

Определение:

Отношение $R(v, u)$ называется отношением слабой связности (англ. weak connectivity), если вершины $u$ и $v$ связаны в неориентированном графе $G'$, полученном из графа $G$ удалением ориентации с рёбер.

Теорема:

Слабая связность является отношением эквивалентности.

Доказательство:

[math]\triangleright[/math]

Аналогично доказательству соответствующей теоремы для неориентированного графа.

[math]\triangleleft[/math]

Пример ориентированного графа с тремя компонентами слабой связности.

Сильная связность

Определение:

Отношение [math]R(v, u) = v \rightsquigarrow u \land u \rightsquigarrow v[/math] на вершинах графа называется отношением сильной связности (англ. strong connectivity).

Теорема:

Сильная связность — отношение эквивалентности.

Доказательство:

[math]\triangleright[/math]

Рефлексивность и симметричность очевидны. Рассмотрим транзитивность: [math](a\rightsquigarrow b \land b\rightsquigarrow a) \land (b\rightsquigarrow c \land c\rightsquigarrow b)\Leftrightarrow (a\rightsquigarrow b \land b\rightsquigarrow c) \land (c\rightsquigarrow b \land b\rightsquigarrow a) \Leftrightarrow a\rightsquigarrow c \land c\rightsquigarrow a[/math]

[math]\triangleleft[/math]

Определение:

Пусть [math]G = (V, E)[/math] — ориентированный граф. Компонентой сильной связности (англ. strongly connected component) называется класс эквивалентности множества вершин этого графа относительно сильной связности.

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

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

Определение:

Ориентированный граф [math]G = (V, E)[/math] называется сильно связным (англ. strongly connected), если он состоит из одной компоненты сильной связности.

См. также

• Отношение рёберной двусвязности
• Отношение вершинной двусвязности

Источники информации

• Отношения связности для вершин неорграфа на ivtb.ru
• Харари Фрэнк Теория графов: Пер. с англ./ Предисл. В. П. Козырева; Под ред. Г.П.Гаврилова. Изд. 4-е. — М.: Книжный дом "ЛИБРОКОМ", 2009. — 296 с. — ISBN 978-5-397-00622-4.