Изменения
→Случай неориентированного графа
== Случай неориентированного графа ==
{{Определение
|definition=
Две вершины <tex>u</tex> и <tex>v</tex> называются '''связанными''Компоненты связности''' неориентированного (англ. adjacent)'', если в графе <tex>G</tex> существует [[Основные определения: граф, ребро, вершина, степень, петля, теории графов|путь, цикл|графа]] из <tex>G=(V, E)u</tex> — такие множества в <tex>C_iv</tex> что (обозначение: <tex>C_i u \subset Vrightsquigarrow v </tex> и между любыми вершинами из одного множества существует [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл#Путь|путь]], а между любыми вершинами из разных множеств - нет).}}
{{Теорема
|statement=
|proof=
}}
{{Определение
|id = def2
|definition=
'''Компонентой связности''' ''(англ. connected component)'' называется класс эквивалентности относительно связности.}}
{{Определение
|id = connected_graph
|definition=
Граф <tex>G=(V, E)</tex> называется '''связным''' ''(англ. connectivity graph)'', если он состоит из одной компоненты связности. В противном случае граф называется '''несвязным'''.}}
== Случай ориентированного графа ==
В общем случае для ориентированного графа существование пути — нетранзитивное не симметричное отношение, поэтому вместо понятия связность связности различают понятие слабой и сильной связности.
=== Слабая связность ===
<wikitex>{{Определение
|definition=
Отношение $R(v, u)$ называется отношением '''слабой связности''' ''(англ. weak connectivity)'', если вершины $u$ и $v$ связаны в неориентированном графе $G'$, полученном из графа $G$ удалением ориентации с рёбер.
}}
{{Теорема
|statement=
Слабая связность '''является [[Отношение_эквивалентности|отношением эквивалентности]]'''.
|proof=
Аналогично доказательству соответствующей теоремы для неориентированного графа.
}}
[[Файл:components1.png|400px|thumb|left|Пример ориентированного графа с тремя компонентами слабой связности.]]
<br clear="all" />
</wikitex>
=== Сильная связность ===
{{Определение
|id=sc_def
|definition=
{{Определение
|definition=
Пусть <tex>G = (V, E)</tex> — [[Основные_определения_теории_графов|ориентированный граф]]. '''Компонента слабой Компонентой сильной связности''' - ''(англ. strongly connected component)'' называется класс эквивалентности множества вершин этого графа <tex>C_i</tex>, на которые разбивает множество <tex>V</tex> отношение существования неориентированного путиотносительно сильной связности.}}[[Файл:Components2.png|400px|thumb|left|Пример ориентированного графа с тремя компонентами сильной связности.]]
{{Определение
|definition=
[[Основные_определения_теории_графов|Ориентированный граф ]] <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.