69
правок
Изменения
Нет описания правки
|definition=
'''Компоненты связности''' неориентированного графа <math>G=(V, E)</math> — такие множества <math>C_i</math> что <math>C_i \subset V</math> и между любыми вершинами из одного множества существует путь, а между любыми вершинами из разных множеств не существует пути}}
{{Теорема
|statement=
Для неориентированного графа <math>G=(V, E)</math> cемейство множеств <math>C_i</math> удовлетворяющих определению единственно и образует разбиение множества <math>V</math>
|proof=
Докажем что отношение существования пути, заданное на множестве вершин графа, разбивает множество <math>V</math> на '''классы эквивалентности''' <br>
'''Рефлексивность''': <math>\forall a \in V a \rightsquigarrow a</math> (Очевидно) <br>
'''Коммутативность''': <math>a\rightsquigarrow b \Rightarrow b\rightsquigarrow a</math> (В силу неориентированности графа)
'''Транзитивность''': <math>a\rightsquigarrow b \and b\rightsquigarrow c \Rightarrow a\rightsquigarrow c</math> (Очевидно)
}}
