355
правок
Изменения
→Связность
== Случай неориентированного графа ==
{{Определение
|definition=
Две вершины <tex>u</tex> и <tex>v</tex> называются '''Компоненты связностисвязными''' неориентированного [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл|графа]] если в графе <tex>G=(V, E)</tex> — такие множества существует путь из <tex>C_iu</tex>, что в <tex>C_i \subset Vv</tex>, и между любыми вершинами из одного множества существует [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл#Путь|путь]], а между любыми вершинами из разных множеств — нет.}}
{{Теорема
|statement=
|proof=
'''Рефлексивность''': <tex>\forall a \in V a \rightsquigarrow a</tex> (очевидно).
'''Симметричность''': <tex>a\rightsquigarrow b \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>u \rightsquigarrow v</tex>.
}}
{{Определение
|definition=
'''Компонентой связности''' называется класс эквивалентности относительно связности.}}
{{Определение
