Relația margine la margine
Conţinut
De la margine la margine [editare]
| Definiție: |
| Două vârfuri [math]u[/math] și [math] v[/math] ale graficului [math]G[/math] se numescedge biconnected(edge edge biconnected), dacă există două căi disjunse între aceste vârfuri. |
| Teorema: |
Reflexivitate:[matematică](u, u)\în R. [/math] (Evident)
Simetrie:[matematică](u, v)\în R \Rightarrow (v, u)\în R. [/math] (Evident)
Tranzitivitate:[matematică](u, v)\în R [/math] și [matematică](v, w)\în R \Rightarrow (u, w)\în R. [/math]
Dovada:Să existe două căi disjunse între muchii de la [math] w [/math] la [math] v [/math], [math] P_1 [/math] și [math] P_2 [/ matematică] respectiv. Notați cu [math] C [/math] unirea a două căi disjunse de muchii de la [math] u [/math] la [math] v [/math] . [math] C [/math] va fi un ciclu simplu de margine. Fie vârfurile [math]a[/math] și [math]b[/math] să fie primele vârfuri din partea lui [math]w[/math] la intersecția lui [math] P_1 [/math] și [ math] P_2 [/math ] cu [math] C [/math] respectiv.