Изменения
Нет описания правки
{{Теорема
|statement=
Связность {{---}} '''[[Отношение_эквивалентности|отношение эквивалентности]]''' (equivalence relation).
|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>.
}}
{{Теорема
|statement=
Слабая связность '''является [[Отношение_эквивалентности|отношением эквивалентности]]'''.
|proof=
Аналогично доказательству соответствующей теоремы для неориентированного графа.
{{Теорема
|statement=
Сильная связность {{---}} '''[[Отношение_эквивалентности|отношение эквивалентности]]'''.
|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>
}}
{{Определение
|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" />
