Изменения

Две вершины <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> и между любыми вершинами из одного множества существует [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл#Путь|путь]], а между любыми вершинами из разных множеств — нет).}} 

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

Докажем что отношение существования пути, заданное на множестве вершин графа, разбивает множество '''[[Рефлексивное_отношение|Рефлексивность]]''': <tex>\forall a \in Va \rightsquigarrow a</tex> на '''классы эквивалентности'''(очевидно).

'''Рефлексивность[[Симметричное_отношение|Симметричность]]''': <tex>a\forall a rightsquigarrow b \in V a 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 ac</tex> (в силу неориентированности графа).}}

{{Определение|id = def2|definition='''ТранзитивностьКомпонентой связности''''': <tex>a\rightsquigarrow b \land b\rightsquigarrow c \Rightarrow a\rightsquigarrow c</tex> (очевидноангл. connected component)'' называется класс эквивалентности относительно связности.}}

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

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

Пусть <tex>G = Отношение $R(Vv, Eu)</tex> — ориентированный граф. Рассмотрим граф <tex>G$ называется отношением ''' = (V, Eслабой связности')</tex>, составленный из вершин графа <tex>G</tex>, в котором ребро <tex>(x, y)</tex> существует тогда и только тогда, когда <tex>(x, y) \in E \lor (y, x) \in E</tex> Скажем что между вершинами <tex>v \in G</tex> и <tex>u \in G</tex> существет '''неориентированный путь'(англ. weak connectivity)'', если <tex>вершины $u$ и $v</tex> и <tex>u</tex> $ связаны путем в <tex>неориентированном графе $G'$, полученном из графа $G$ удалением ориентации с рёбер.}} {{Теорема|statement=Слабая связность '''является [[Отношение_эквивалентности|отношением эквивалентности]]'''.|proof=Аналогично доказательству соответствующей теоремы для неориентированного графа.}}[[Файл:components1.png|400px|thumb|left|Пример ориентированного графа с тремя компонентами слабой связности.]]<br clear="all" /tex>.}} === Сильная связность ===

Пусть Отношение <tex>G = R(Vv, Eu)= v \rightsquigarrow u \land u \rightsquigarrow v</tex> — ориентированный граф. на вершинах графа называется отношением '''Компонента слабой сильной связности''' - класс эквивалентности вершин графа <tex>C_i</tex>, на которые разбивает множество <tex>V</tex> отношение существования неориентированного пути''(англ. strong connectivity)''.}} {{Теорема|statement=Сильная связность {{Определение---}} '''[[Отношение_эквивалентности|отношение эквивалентности]]'''.|definitionproof=Ориентированный граф '''[[Рефлексивное_отношение|Рефлексивность]]''' и '''[[Симметричное_отношение|симметричность]]''' очевидны. Рассмотрим '''[[Транзитивное_отношение|транзитивность]]''': <tex>G = (V, Ea\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> называется '''слабо связным''', если он состоит из одной компоненты слабой связности.}}

Пусть <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. [[Категория:Алгоритмы и структуры данных]][[Категория:Связность в графах]]