Изменения

Две вершины <mathtex>U</mathtex> и <mathtex> V</mathtex> графа <mathtex>G</mathtex> называются '''реберно двусвязными''', если между этими вершинами существуют два реберно не пересекающихся пути.

Пусть <mathtex>R</mathtex> - отношение реберной двусвязности.

'''Рефлексивность:''' <mathtex>(u, u)\in R. </mathtex> (Очевидно)

'''Коммутативность:''' <mathtex>(u, v)\in R \Rightarrow (v, u)\in R. </mathtex> (Очевидно)

'''Транзитивность:''' <mathtex>(u, v)\in R </mathtex> и <mathtex>(v, w)\in R \Rightarrow (u, w)\in R. </mathtex>

''Доказательство:'' Пусть <mathtex>P_1,P_2 = u \rightsquigarrow v</mathtex>(реберно не пересекающиеся пути) и <mathtex>Q_1,Q_2 = v \rightsquigarrow w</mathtex> (реберно не пересекающиеся пути).

Выберем вершины <mathtex>x_1</mathtex> и <mathtex>x_2</mathtex> так, что <mathtex>P_1 \and land Q_1 = (v \rightsquigarrow x_1),</mathtex> <mathtex>P_2 \and land Q_2 = (v \rightsquigarrow x_2)</mathtex> и <mathtex>(v \rightsquigarrow x_1) \and land (v \rightsquigarrow x_2) = v.</mathtex>

Получим два реберно не пересекающихся пути <mathtex>R_1 = (u \rightsquigarrow x_1) \or lor (x_1 \rightsquigarrow w) </mathtex> и <mathtex>R_2 = (u \rightsquigarrow x_2) \or lor (x_2 \rightsquigarrow w). </mathtex>

Действительно, <mathtex> (u \rightsquigarrow x_1) \and land (u \rightsquigarrow x_2) = u</mathtex>(реберная двусвязность <mathtex>u</mathtex> и <mathtex>v</mathtex>). <mathtex> (x_1 \rightsquigarrow w) \and land (x_2 \rightsquigarrow w) = w</mathtex>(реберная двусвязность <mathtex>v</mathtex> и <mathtex>w</mathtex>)Если <mathtex>(u \rightsquigarrow x_1) \and land (x_2 \rightsquigarrow w)= </mathtex> {какой-то путь} или <mathtex>(u \rightsquigarrow x_2) \and land (x_1 \rightsquigarrow w)= </mathtex> {какой-то путь}, то тогда вершины <mathtex>v</mathtex> и <mathtex> w</mathtex> не связаны отношением реберной двусвязности.