Връзката от край до край
Съдържание
От край до край [редактиране]
| Определение: |
| Два върха [math]u[/math] и [math] v[/math] на графиката [math]G[/math] се наричат двусвързани ръбове(англ. edge biconnected), ако между тези върхове има два пътя с различни ръбове. |
| Теорема: |
Рефлексивност:[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] w [/math] до [math] v [/math], [math] P_1 [/math] и [math] P_2 [/math] съответно. Означете с [math] C [/math] обединението на два пътя с различни ръбове от [math] u [/math] до [math] v [/math] . [math] C [/math] ще бъде цикъл с прост ръб. Нека върховете [math]a[/math] и [math]b[/math] са първите върхове от страната на [math]w[/math] в пресечната точка на [math] P_1 [/math] и [math] P_2 [/math] с [math] C [/math], съответно.