Отношение связности, компоненты связности — различия между версиями
Smolcoder (обсуждение | вклад) (→Слабая связность) |
м (rollbackEdits.php mass rollback) |
||
| (не показано 57 промежуточных версий 22 участников) | |||
| Строка 1: | Строка 1: | ||
== Случай неориентированного графа == | == Случай неориентированного графа == | ||
| + | |||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
| − | Две вершины <tex>u</tex> и <tex>v</tex> называются ''' | + | Две вершины <tex>u</tex> и <tex>v</tex> называются '''связанными''' ''(англ. adjacent)'', если в графе <tex>G</tex> существует [[Основные определения теории графов|путь]] из <tex>u</tex> в <tex>v</tex> (обозначение: <tex>u \rightsquigarrow v </tex>).}} |
{{Теорема | {{Теорема | ||
|statement= | |statement= | ||
| − | Связность - '''отношение эквивалентности'''. | + | Связность {{---}} '''[[Отношение_эквивалентности|отношение эквивалентности]]''' ''(англ. equivalence relation)''. |
|proof= | |proof= | ||
| − | '''Рефлексивность''': <tex>\forall a \in V a \rightsquigarrow a</tex> (очевидно). | + | '''[[Рефлексивное_отношение|Рефлексивность]]''': <tex>\forall a \in V a \rightsquigarrow a</tex> (очевидно). |
| − | '''Симметричность''': <tex>a\rightsquigarrow b \Rightarrow b\rightsquigarrow a</tex> (в силу неориентированности графа). | + | '''[[Симметричное_отношение|Симметричность]]''': <tex>a\rightsquigarrow b \Rightarrow b\rightsquigarrow a</tex> (в силу неориентированности графа). |
| − | '''Транзитивность''': <tex>a\rightsquigarrow b \land b\rightsquigarrow c \Rightarrow a\rightsquigarrow c</tex>. Действительно, сначала пройдем от <tex>a</tex> до <tex>b</tex>, затем от <tex>b</tex> до <tex>c</tex>, что и означает существования пути <tex>a \rightsquigarrow | + | '''[[Транзитивное_отношение|Транзитивность]]''': <tex>a\rightsquigarrow b \land b\rightsquigarrow c \Rightarrow a\rightsquigarrow c</tex>. Действительно, сначала пройдем от <tex>a</tex> до <tex>b</tex>, затем от <tex>b</tex> до <tex>c</tex>, что и означает существования пути <tex>a \rightsquigarrow c</tex>. |
}} | }} | ||
{{Определение | {{Определение | ||
| + | |id = def2 | ||
|definition= | |definition= | ||
| − | '''Компонентой связности''' называется класс эквивалентности относительно связности.}} | + | '''Компонентой связности''' ''(англ. connected component)'' называется класс эквивалентности относительно связности.}} |
{{Определение | {{Определение | ||
| + | |id = connected_graph | ||
|definition= | |definition= | ||
| − | Граф <tex>G=(V, E)</tex> называется '''связным''', если он состоит из одной компоненты связности. В противном случае граф называется '''несвязным'''.}} | + | Граф <tex>G=(V, E)</tex> называется '''связным''' ''(англ. connectivity graph)'', если он состоит из одной компоненты связности. В противном случае граф называется '''несвязным'''.}} |
== Случай ориентированного графа == | == Случай ориентированного графа == | ||
В общем случае для ориентированного графа существование пути — не симметричное отношение, поэтому вместо понятия связности различают понятие слабой и сильной связности. | В общем случае для ориентированного графа существование пути — не симметричное отношение, поэтому вместо понятия связности различают понятие слабой и сильной связности. | ||
=== Слабая связность === | === Слабая связность === | ||
| − | + | {{Определение | |
|definition= | |definition= | ||
| − | Отношение $R(v, u)$ называется отношением '''слабой связности''', если вершины $u$ и $v$ связаны в графе $G'$, полученном из графа $G$ | + | Отношение $R(v, u)$ называется отношением '''слабой связности''' ''(англ. weak connectivity)'', если вершины $u$ и $v$ связаны в неориентированном графе $G'$, полученном из графа $G$ удалением ориентации с рёбер. |
}} | }} | ||
{{Теорема | {{Теорема | ||
|statement= | |statement= | ||
| − | Слабая связность '''является отношением эквивалентности'''. | + | Слабая связность '''является [[Отношение_эквивалентности|отношением эквивалентности]]'''. |
|proof= | |proof= | ||
Аналогично доказательству соответствующей теоремы для неориентированного графа. | Аналогично доказательству соответствующей теоремы для неориентированного графа. | ||
}} | }} | ||
| − | </ | + | [[Файл:components1.png|400px|thumb|left|Пример ориентированного графа с тремя компонентами слабой связности.]] |
| + | <br clear="all" /> | ||
=== Сильная связность === | === Сильная связность === | ||
{{Определение | {{Определение | ||
| + | |id=sc_def | ||
|definition= | |definition= | ||
| − | Отношение <tex>R(v, u) = v \rightsquigarrow u \land u \rightsquigarrow v</tex> на вершинах графа называется отношением '''сильной связности'''. | + | Отношение <tex>R(v, u) = v \rightsquigarrow u \land u \rightsquigarrow v</tex> на вершинах графа называется отношением '''сильной связности''' ''(англ. strong connectivity)''. |
}} | }} | ||
{{Теорема | {{Теорема | ||
|statement= | |statement= | ||
| − | Сильная связность - '''отношение эквивалентности'''. | + | Сильная связность {{---}} '''[[Отношение_эквивалентности|отношение эквивалентности]]'''. |
|proof= | |proof= | ||
| − | '''Рефлексивность''' и '''симметричность''' очевидны. Рассмотрим '''транзитивность''': | + | '''[[Рефлексивное_отношение|Рефлексивность]]''' и '''[[Симметричное_отношение|симметричность]]''' очевидны. Рассмотрим '''[[Транзитивное_отношение|транзитивность]]''': |
<tex>(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</tex> | <tex>(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</tex> | ||
}} | }} | ||
| Строка 55: | Строка 60: | ||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
| − | Пусть <tex>G = (V, E)</tex> — ориентированный граф. '''Компонентой сильной связности''' называется класс эквивалентности множества вершин этого графа относительно сильной связности.}} | + | Пусть <tex>G = (V, E)</tex> — [[Основные_определения_теории_графов|ориентированный граф]]. '''Компонентой сильной связности''' ''(англ. strongly connected component)'' называется класс эквивалентности множества вершин этого графа относительно сильной связности.}} |
| + | Компоненты сильной связности могут быть найдены [[Использование обхода в глубину для поиска компонент сильной связности|с помощью обхода в глубину]]. | ||
| + | [[Файл:Components2.png|400px|thumb|left|Пример ориентированного графа с тремя компонентами сильной связности.]] | ||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
| − | Ориентированный граф <tex>G = (V, E)</tex> называется '''сильно связным''', если он состоит из одной компоненты сильной связности.}} | + | [[Основные_определения_теории_графов|Ориентированный граф]] <tex>G = (V, E)</tex> называется '''сильно связным''' ''(англ. strongly connected)'', если он состоит из одной компоненты сильной связности.}} |
| + | |||
| + | <br clear="all" /> | ||
| + | |||
| + | ==См. также== | ||
| + | |||
| + | *[[Отношение рёберной двусвязности]] | ||
| + | *[[Отношение вершинной двусвязности]] | ||
| + | |||
| + | ==Источники информации== | ||
| + | * [http://xn--90abr5b.xn--p1ai/wiki/doku.php?id=examination:diskretka:question12 Отношения связности для вершин неорграфа на ivtb.ru] | ||
| + | * Харари Фрэнк '''Теория графов''': Пер. с англ./ Предисл. В. П. Козырева; Под ред. Г.П.Гаврилова. Изд. 4-е. — М.: Книжный дом "ЛИБРОКОМ", 2009. — 296 с. — ISBN 978-5-397-00622-4. | ||
| + | |||
| + | [[Категория:Алгоритмы и структуры данных]] | ||
| + | [[Категория:Связность в графах]] | ||
Текущая версия на 19:30, 4 сентября 2022
Содержание
Случай неориентированного графа
| Определение: |
| Две вершины и называются связанными (англ. 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.
