Изменения

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

Для неориентированного графа <tex>G=(V, E)</tex> cемейство множеств <tex>C_i</tex> удовлетворяющих определению единственно и образует разбиение множества <tex>V</tex>.

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

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

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

Пусть <tex>G = (V, E)</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> существет '''неориентированный путь''', если <tex>v</tex> и <tex>u</tex> связаны путем в <tex>G'</tex> .}}

Пусть <tex>G = (V, E)</tex> — ориентированный граф. '''Компонента слабой связности''' - класс эквивалентности вершин графа <tex>C_i</tex>, на которые разбивает множество <tex>V</tex> отношение существования неориентированного пути.}}

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

Пусть <tex>G = (V, E)</tex> — ориентированный граф. '''Компонента сильной связности''' - класс эквивалентности вершин графа <tex>C_i</tex>, на которые разбивает множество <tex>V</tex> отношение существования пути между вершинами в обе стороны.}}

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