Граф компонент рёберной двусвязности

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

Пусть граф [math]G[/math] реберно двусвязен. Обозначим [math]A_1...A_n[/math] - компоненты реберной двусвязности, а [math]a_1...a_m[/math] - мосты [math]G[/math]. Построим граф [math]T[/math], в котором вершинами будут [math]A_1...A_n[/math], а ребрами [math]a_1...a_m[/math], соединяющими соответствующие вершины из соответствующих компонент реберной двусвязности. Полученный граф [math]T[/math] называют графом компонент реберной двусвязности графа [math]G[/math].

Лемма:

В определениях, приведенных выше, [math]T[/math] - дерево.

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

[math]\triangleright[/math]

[math]\land[/math] - пересечение путей. [math]A \land B : (a, b) \in A \land B \Rightarrow (a, b) \in A \land (a, b) \in B[/math] а) [math]T[/math] - связно. (Следует из определения) б) В [math]T[/math] нет циклов. Пусть какие-то две смежные вершины [math]A_k[/math] и [math]A_l[/math] принадлежат какому-то циклу. Тогда ребро [math](A_k, A_l)[/math] принадлежит этому же циклу. Следовательно, существуют два реберно не пересекающихся пути между вершинами [math]A_k[/math] и [math]A_l[/math], т.е. [math](A_k, A_l)[/math] - не является мостом. Но [math](A_k, A_l)[/math] - мост по условию. Получили противоречие. [math]T[/math] - дерево.

[math]\triangleleft[/math]

См. также

Граф блоков-точек сочленения