Отношение связности, компоненты связности
Содержание
Случай неориентированного графа
Определение: |
Две вершины путь из в (обозначение: ). | и называются связанными (англ. adjacent), если в графе существует
Теорема: |
Связность — отношение эквивалентности (англ. equivalence relation). |
Доказательство: |
Рефлексивность: (очевидно). Симметричность: (в силу неориентированности графа). Транзитивность: . Действительно, сначала пройдем от до , затем от до , что и означает существования пути . |
Определение: |
Компонентой связности (англ. connected component) называется класс эквивалентности относительно связности. |
Определение: |
Граф | называется связным (англ. connectivity graph), если он состоит из одной компоненты связности. В противном случае граф называется несвязным.
Случай ориентированного графа
В общем случае для ориентированного графа существование пути — не симметричное отношение, поэтому вместо понятия связности различают понятие слабой и сильной связности.
Слабая связность
Определение: |
Отношение $R(v, u)$ называется отношением слабой связности (англ. weak connectivity), если вершины $u$ и $v$ связаны в неориентированном графе $G'$, полученном из графа $G$ удалением ориентации с рёбер. |
Теорема: |
Слабая связность является отношением эквивалентности. |
Доказательство: |
Аналогично доказательству соответствующей теоремы для неориентированного графа. |
Сильная связность
Определение: |
Отношение | на вершинах графа называется отношением сильной связности (англ. strong connectivity).
Теорема: |
Сильная связность — отношение эквивалентности. |
Доказательство: |
Рефлексивность и симметричность очевидны. Рассмотрим транзитивность: |
Определение: |
Пусть ориентированный граф. Компонентой сильной связности (англ. strongly connected component) называется класс эквивалентности множества вершин этого графа относительно сильной связности. | —
Компоненты сильной связности могут быть найдены с помощью обхода в глубину.
Определение: |
Ориентированный граф называется сильно связным (англ. strongly connected), если он состоит из одной компоненты сильной связности. |
См. также
Источники информации
- Отношения связности для вершин неорграфа на ivtb.ru
- Харари Фрэнк Теория графов: Пер. с англ./ Предисл. В. П. Козырева; Под ред. Г.П.Гаврилова. Изд. 4-е. — М.: Книжный дом "ЛИБРОКОМ", 2009. — 296 с. — ISBN 978-5-397-00622-4.