http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&feedformat=atom&user=193.200.211.75&*Викиконспекты - Вклад участника [ru]2026-05-07T17:38:14ZВклад участникаMediaWiki 1.30.0http://neerc.ifmo.ru/wiki/index.php?title=%D0%9E%D1%82%D0%BD%D0%BE%D1%88%D0%B5%D0%BD%D0%B8%D0%B5_%D1%81%D0%B2%D1%8F%D0%B7%D0%BD%D0%BE%D1%81%D1%82%D0%B8,_%D0%BA%D0%BE%D0%BC%D0%BF%D0%BE%D0%BD%D0%B5%D0%BD%D1%82%D1%8B_%D1%81%D0%B2%D1%8F%D0%B7%D0%BD%D0%BE%D1%81%D1%82%D0%B8&diff=72684Отношение связности, компоненты связности2020-02-17T06:21:08Z<p>193.200.211.75: /* Случай неориентированного графа */</p>
<hr />
<div>== Случай неориентированного графа ==<br />
<br />
{{Определение<br />
|definition=<br />
Две вершины <tex>u</tex> и <tex>v</tex> называются '''связанными''' ''(англ. adjacent)'', если в графе <tex>G</tex> существует [[Основные определения теории графов|путь]] из <tex>u</tex> в <tex>v</tex> (обозначение: <tex>u \rightsquigarrow v </tex>).}}<br />
<br />
{{Теорема<br />
|statement=<br />
Связность {{---}} '''[[Отношение_эквивалентности|отношение эквивалентности]]''' ''(англ. equivalence relation)''.<br />
|proof=<br />
'''[[Рефлексивное_отношение|Рефлексивность]]''': <tex>\forall a \in V a \rightsquigarrow a</tex> (очевидно).<br />
<br />
'''[[Симметричное_отношение|Симметричность]]''': <tex>a\rightsquigarrow b \Rightarrow b\rightsquigarrow a</tex> (в силу неориентированности графа).<br />
<br />
'''[[Транзитивное_отношение|Транзитивность]]''': <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>.<br />
}}<br />
<br />
{{Определение<br />
|id = def2<br />
|definition=<br />
'''Компонентой связности''' ''(англ. connected component)'' называется класс эквивалентности относительно связности.}}<br />
<br />
{{Определение<br />
|id = connected_graph<br />
|definition=<br />
Граф <tex>G=(V, E)</tex> называется '''связным''' ''(англ. connectivity graph)'', если он состоит из одной компоненты связности. В противном случае граф называется '''несвязным'''.}}<br />
<br />
== Случай ориентированного графа ==<br />
В общем случае для ориентированного графа существование пути — не симметричное отношение, поэтому вместо понятия связности различают понятие слабой и сильной связности.<br />
=== Слабая связность ===<br />
<wikitex>{{Определение<br />
|definition=<br />
Отношение $R(v, u)$ называется отношением '''слабой связности''' ''(англ. weak connectivity)'', если вершины $u$ и $v$ связаны в неориентированном графе $G'$, полученном из графа $G$ удалением ориентации с рёбер.<br />
}}<br />
<br />
{{Теорема<br />
|statement=<br />
Слабая связность '''является [[Отношение_эквивалентности|отношением эквивалентности]]'''.<br />
|proof=<br />
Аналогично доказательству соответствующей теоремы для неориентированного графа.<br />
}}<br />
[[Файл:components1.png|400px|thumb|left|Пример ориентированного графа с тремя компонентами слабой связности.]]<br />
<br clear="all" /><br />
</wikitex><br />
<br />
=== Сильная связность ===<br />
{{Определение<br />
|id=sc_def<br />
|definition=<br />
Отношение <tex>R(v, u) = v \rightsquigarrow u \land u \rightsquigarrow v</tex> на вершинах графа называется отношением '''сильной связности''' ''(англ. strong connectivity)''.<br />
}}<br />
<br />
{{Теорема<br />
|statement=<br />
Сильная связность {{---}} '''[[Отношение_эквивалентности|отношение эквивалентности]]'''.<br />
|proof=<br />
'''[[Рефлексивное_отношение|Рефлексивность]]''' и '''[[Симметричное_отношение|симметричность]]''' очевидны. Рассмотрим '''[[Транзитивное_отношение|транзитивность]]''': <br />
<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><br />
}}<br />
<br />
{{Определение<br />
|definition=<br />
Пусть <tex>G = (V, E)</tex> — [[Основные_определения_теории_графов|ориентированный граф]]. '''Компонентой сильной связности''' ''(англ. strongly connected component)'' называется класс эквивалентности множества вершин этого графа относительно сильной связности.}}<br />
[[Файл:Components2.png|400px|thumb|left|Пример ориентированного графа с тремя компонентами сильной связности.]]<br />
{{Определение<br />
|definition=<br />
[[Основные_определения_теории_графов|Ориентированный граф]] <tex>G = (V, E)</tex> называется '''сильно связным''' ''(англ. strongly connected)'', если он состоит из одной компоненты сильной связности.}}<br />
<br />
<br clear="all" /><br />
<br />
==См. также==<br />
<br />
*[[Отношение рёберной двусвязности]]<br />
*[[Отношение вершинной двусвязности]]<br />
<br />
==Источники информации==<br />
* [http://xn--90abr5b.xn--p1ai/wiki/doku.php?id=examination:diskretka:question12 Отношения связности для вершин неорграфа на ivtb.ru]<br />
* Харари Фрэнк '''Теория графов''': Пер. с англ./ Предисл. В. П. Козырева; Под ред. Г.П.Гаврилова. Изд. 4-е. — М.: Книжный дом "ЛИБРОКОМ", 2009. — 296 с. — ISBN 978-5-397-00622-4.<br />
<br />
[[Категория:Алгоритмы и структуры данных]]<br />
[[Категория:Связность в графах]]</div>193.200.211.75