Изменения
Нет описания правки
Отношение реберной двусвязности является отношением эквивалентности на вершинах.
|proof=
Операция <tex>A \land B : (a, b) \in A \land B \Rightarrow (a, b) \in A \land (a, b) \in B</tex>
Пусть <tex>R</tex> - отношение реберной двусвязности.
'''Транзитивность:''' <tex>(u, v)\in R </tex> и <tex>(v, w)\in R \Rightarrow (u, w)\in R. </tex>
''Доказательство:'' Пусть <tex>P_1,P_2 = : u \rightsquigarrow v</tex>(реберно не пересекающиеся пути) и <tex>Q_1,Q_2 = : v \rightsquigarrow w</tex> (реберно не пересекающиеся пути).
Выберем вершины <tex>x_1</tex> и <tex>x_2</tex> так, что <tex>P_1 \land Q_1 = (v \rightsquigarrow x_1),</tex> <tex>P_2 \land Q_2 = (v \rightsquigarrow x_2)</tex> и <tex>(v \rightsquigarrow x_1) \land (v \rightsquigarrow x_2) = v.</tex>
Получим два реберно не пересекающихся пути <tex>R_1 = (u \rightsquigarrow x_1) \lor o (x_1 \rightsquigarrow w) </tex> и <tex>R_2 = (u \rightsquigarrow x_2) \lor o (x_2 \rightsquigarrow w). </tex>
Действительно, <tex> (u \rightsquigarrow x_1) \land (u \rightsquigarrow x_2) = u</tex>(реберная двусвязность <tex>u</tex> и <tex>v</tex>). <tex> (x_1 \rightsquigarrow w) \land (x_2 \rightsquigarrow w) = w</tex>(реберная двусвязность <tex>v</tex> и <tex>w</tex>)
Если <tex>(u \rightsquigarrow x_1) \land (x_2 \rightsquigarrow w)= </tex> {какой-то путь} или <tex>(u \rightsquigarrow x_2) \land (x_1 \rightsquigarrow w)= </tex> {какой-то путь}, то тогда вершины <tex>v</tex> и <tex> w</tex> не связаны отношением реберной двусвязности.
}}
