Редактирование: Отношение связности, компоненты связности
Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
| Текущая версия | Ваш текст | ||
| Строка 3: | Строка 3: | ||
{{Определение | {{Определение | ||
|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>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 c</tex>. |
}} | }} | ||
| Строка 19: | Строка 19: | ||
|id = def2 | |id = def2 | ||
|definition= | |definition= | ||
| − | '''Компонентой связности | + | '''Компонентой связности''' (connected component) называется класс эквивалентности относительно связности.}} |
{{Определение | {{Определение | ||
| − | |||
|definition= | |definition= | ||
| − | Граф <tex>G=(V, E)</tex> называется '''связным | + | Граф <tex>G=(V, E)</tex> называется '''связным''' (connectivity graph), если он состоит из одной компоненты связности. В противном случае граф называется '''несвязным'''.}} |
== Случай ориентированного графа == | == Случай ориентированного графа == | ||
| Строка 31: | Строка 30: | ||
<wikitex>{{Определение | <wikitex>{{Определение | ||
|definition= | |definition= | ||
| − | Отношение $R(v, u)$ называется отношением '''слабой связности | + | Отношение $R(v, u)$ называется отношением '''слабой связности''' (weak connectivity), если вершины $u$ и $v$ связаны в неориентированном графе $G'$, полученном из графа $G$ удалением ориентации с рёбер. |
}} | }} | ||
{{Теорема | {{Теорема | ||
|statement= | |statement= | ||
| − | Слабая связность '''является | + | Слабая связность '''является отношением эквивалентности'''. |
|proof= | |proof= | ||
Аналогично доказательству соответствующей теоремы для неориентированного графа. | Аналогично доказательству соответствующей теоремы для неориентированного графа. | ||
| Строка 48: | Строка 47: | ||
|id=sc_def | |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> | ||
}} | }} | ||
| Строка 61: | Строка 60: | ||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
| − | Пусть <tex>G = (V, E)</tex> — | + | Пусть <tex>G = (V, E)</tex> — ориентированный граф. '''Компонентой сильной связности''' называется класс эквивалентности множества вершин этого графа относительно сильной связности.}} |
[[Файл:Components2.png|400px|thumb|left|Пример ориентированного графа с тремя компонентами сильной связности.]] | [[Файл:Components2.png|400px|thumb|left|Пример ориентированного графа с тремя компонентами сильной связности.]] | ||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
| − | + | Ориентированный граф <tex>G = (V, E)</tex> называется '''сильно связным''', если он состоит из одной компоненты сильной связности.}} | |
<br clear="all" /> | <br clear="all" /> | ||
| − | + | ==Источники== | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | ==Источники | ||
* [http://xn--90abr5b.xn--p1ai/wiki/doku.php?id=examination:diskretka:question12 Отношения связности для вершин неорграфа на ivtb.ru] | * [http://xn--90abr5b.xn--p1ai/wiki/doku.php?id=examination:diskretka:question12 Отношения связности для вершин неорграфа на ivtb.ru] | ||
* Харари Фрэнк '''Теория графов''': Пер. с англ./ Предисл. В. П. Козырева; Под ред. Г.П.Гаврилова. Изд. 4-е. — М.: Книжный дом "ЛИБРОКОМ", 2009. — 296 с. — ISBN 978-5-397-00622-4. | * Харари Фрэнк '''Теория графов''': Пер. с англ./ Предисл. В. П. Козырева; Под ред. Г.П.Гаврилова. Изд. 4-е. — М.: Книжный дом "ЛИБРОКОМ", 2009. — 296 с. — ISBN 978-5-397-00622-4. | ||
