Изменения

'''Компоненты связности''' неориентированного [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл|графа]] <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> на '''классы эквивалентности'''.

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

Пусть <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>C_i</tex>, на которые разбивает множество <tex>V</tex> отношение существования пути между вершинами в обе стороны.}}