Изменения

Две вершины <tex>u</tex> и <tex>v</tex> называются '''Компоненты связностисвязаными''' неориентированного графа ''(англ. adjacent)'', если в графе <mathtex>G=(V, E)</mathtex> существует [[Основные определения теории графов|путь]] из <tex>u</tex> — такие множества в <mathtex>C_iv</mathtex> что (обозначение: <mathtex>C_i u \subset Vrightsquigarrow v </mathtex> и между любыми вершинами из одного множества существует путь, а между любыми вершинами из разных множеств не существует пути).}} 

Для неориентированного графа <math>G=Связность {{---}} '''[[Отношение_эквивалентности|отношение эквивалентности]]''' ''(V, Eангл. equivalence relation)</math> cемейство множеств <math>C_i</math> удовлетворяющих определению единственно и образует разбиение множества <math>V</math>''.

Докажем что отношение существования пути, заданное на множестве вершин графа, разбивает множество <math>V</math> на '''классы эквивалентности''' <br>'''[[Рефлексивное_отношение|Рефлексивность]]''': <mathtex>\forall a \in V a \rightsquigarrow a</mathtex> (Очевидноочевидно) <br>. '''Коммутативность[[Симметричное_отношение|Симметричность]]''': <mathtex>a\rightsquigarrow b \Rightarrow b\rightsquigarrow a</mathtex> (В в силу неориентированности графа). '''[[Транзитивное_отношение|Транзитивность]]''': <mathtex>a\rightsquigarrow b \and land b\rightsquigarrow c \Rightarrow a\rightsquigarrow c</mathtex>. Действительно, сначала пройдем от <tex>a</tex> до <tex>b</tex>, затем от <tex>b</tex> до <tex>c</tex>, что и означает существования пути <tex>a \rightsquigarrow c</tex> (Очевидно).

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

В общем случае для ориентированного графа существование пути — нетранзитивное не симметричное отношение, поэтому вместо понятия связность связности различают понятие слабой и сильной связности.

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

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

[[Основные_определения_теории_графов|Ориентированный граф ]] <mathtex>G = (V, E)</mathtex> называется '''слабо сильно связным''' ''(англ. 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.

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