Изменения

Перейти к: навигация, поиск

Отношение связности, компоненты связности

42 байта убрано, 09:21, 17 февраля 2020
Случай неориентированного графа
{{Определение
|definition=
Две вершины <tex>u</tex> и <tex>v</tex> называются '''связанымисвязанными''' ''(англ. adjacent)'', если в графе <tex>G</tex> существует [[Основные определения теории графов|путь]] из <tex>u</tex> в <tex>v</tex> (обозначение: <tex>u \rightsquigarrow v </tex>).}}
{{Теорема
|statement=
Связность {{---}} '''[[Отношение_эквивалентности|отношение эквивалентности]]''' ''(англ. equivalence relation)''.
|proof=
'''[[Рефлексивное_отношение|Рефлексивность]]''': <tex>\forall a \in V a \rightsquigarrow a</tex> (очевидно).
|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$ удалением ориентации с рёбер.
}}
|id=sc_def
|definition=
Отношение <tex>R(v, u) = v \rightsquigarrow u \land u \rightsquigarrow v</tex> на вершинах графа называется отношением '''сильной связности''' ''(англ. strong connectivity)''.
}}
{{Определение
|definition=
Пусть <tex>G = (V, E)</tex> — [[Основные_определения_теории_графов|ориентированный граф]]. '''Компонентой сильной связности''' ''(англ. strongly connected component)'' называется класс эквивалентности множества вершин этого графа относительно сильной связности.}}
[[Файл:Components2.png|400px|thumb|left|Пример ориентированного графа с тремя компонентами сильной связности.]]
{{Определение
|definition=
[[Основные_определения_теории_графов|Ориентированный граф]] <tex>G = (V, E)</tex> называется '''сильно связным''' ''(англ. strongly connected)'', если он состоит из одной компоненты сильной связности.}}
<br clear="all" />
==См. также==
*[[Отношение_реберной_двусвязности|Отношение_реберной_двусвязностиОтношение рёберной двусвязности]]*[[Отношение_вершинной_двусвязности|Отношение_вершинной_двусвязностиОтношение вершинной двусвязности]]
==Источники информации==
Анонимный участник

Навигация