Изменения

Две вершины <tex>u</tex> и <tex>v</tex> называются '''связнымисвязаными''' ''(англ. adjacent)'', если в графе <tex>G</tex> существует [[Основные определения теории графов|путь ]] из <tex>u</tex> в <tex>v</tex>(обозначение: <tex>u \rightsquigarrow v </tex>).}}

Связность {{- --}} '''[[Отношение_эквивалентности|отношение эквивалентности]]''' ''(англ. equivalence relation)''.

'''[[Рефлексивное_отношение|Рефлексивность]]''': <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>u a \rightsquigarrow vc</tex>.

'''Компонентой связности''' ''(англ. connected component)'' называется класс эквивалентности относительно связности.}}

Граф <tex>G=(V, E)</tex> называется '''связным''' ''(англ. connectivity graph)'', если он состоит из одной компоненты связности. В противном случае граф называется '''несвязным'''.}}

Пусть Отношение <tex>G = R(Vv, Eu)= v \rightsquigarrow u \land u \rightsquigarrow v</tex> — ориентированный графна вершинах графа называется отношением '''сильной связности''' ''(англ. strong connectivity)''.}} {{Теорема|statement=Сильная связность {{---}} '''[[Отношение_эквивалентности|отношение эквивалентности]]'''.|proof='''[[Рефлексивное_отношение|Рефлексивность]]''' и '''[[Симметричное_отношение|симметричность]]''' очевидны. Рассмотрим граф <tex>G' = (V, E')</tex>, составленный из вершин графа <tex>G</tex>, в котором ребро '[[Транзитивное_отношение|транзитивность]]''': <tex>(x, ya\rightsquigarrow b \land b\rightsquigarrow a)</tex> существует тогда и только тогда, когда <tex>\land (x, yb\rightsquigarrow c \land c\rightsquigarrow b) \in E Leftrightarrow (a\lor rightsquigarrow b \land b\rightsquigarrow c) \land (y, xc\rightsquigarrow b \land b\rightsquigarrow a) \in E</tex>. Скажем, что между вершинами <tex>v Leftrightarrow a\rightsquigarrow c \in G</tex> и <tex>u land c\in Grightsquigarrow a</tex> существет '''неориентированный путь''', если <tex>v</tex> и <tex>u</tex> связаны путем в <tex>G'</tex>.}} 

Пусть <tex>G = (V, E)</tex> — [[Основные_определения_теории_графов|ориентированный граф]]. '''Компоненты слабой Компонентой сильной связности''' — классы ''(англ. strongly connected component)'' называется класс эквивалентности множества вершин этого графа <tex>C_i</tex>, на которые разбивает множество <tex>V</tex> отношение существования неориентированного путиотносительно сильной связности.}}[[Файл:Components2.png|400px|thumb|left|Пример ориентированного графа с тремя компонентами сильной связности.]]

[[Основные_определения_теории_графов|Ориентированный граф ]] <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.

=== Сильная связность ===[[Категория:Алгоритмы и структуры данных]]Пусть <tex>G=(V, E) </tex> — ориентированный граф. Введем отношение на вершинах графа[[Категория: <tex>R(v, u) = v \rightsquigarrow u \land u \rightsquigarrow v</tex>. Очевидно, <tex>R</tex> рефлексивно, коммутативно, транзитивно.{{Определение|definition=Пусть <tex>G = (V, E)</tex> — ориентированный граф. '''Компоненты сильной связности''' — классы эквивалентности вершин графа <tex>C_i</tex>, на которые разбивает множество <tex>V</tex> отношение существования пути между вершинами Связность в обе стороны.}}{{Определение|definition=Ориентированный граф <tex>G = (V, E)</tex> называется '''сильно связным''', если он состоит из одной компоненты сильной связности.}}графах]]