Отношение рёберной двусвязности

Реберная двусвязность

Определение:

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

Теорема:

Отношение реберной двусвязности является отношением эквивалентности на вершинах.

Доказательство:

[math]\triangleright[/math]

Пусть [math]R[/math] - отношение реберной двусвязности. Рефлексивность: [math](u, u)\in R. [/math] (Очевидно) Коммутативность: [math](u, v)\in R \Rightarrow (v, u)\in R. [/math] (Очевидно) Транзитивность: [math](u, v)\in R [/math] и [math](v, w)\in R \Rightarrow (u, w)\in R. [/math] Доказательство: Пусть [math]P_1,P_2 = u \rightsquigarrow v[/math] и [math]Q_1,Q_2 = v \rightsquigarrow w[/math] - реберно непересекащиеся пути.

[math]\triangleleft[/math]