205
правок
Изменения
Нет описания правки
{{Определение
|definition=
Пусть граф <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>.
}}
{{Лемма
|statement=
В определениях, приведенных выше, <math>T</math> - дерево.
|proof=
''а)'' <math>T</math> - связно. (Следует из определения)
''б)'' В <math>T</math> нет циклов.
Пусть какие-то две последовательные вершины <math>A_k</math> и <math>A_l</math> принадлежат какому-то циклу. Тогда ребро <math>(A_k, A_l)</math> принадлежит этому же циклу.
Следовательно, <math>\exist</math> два реберно неперескающихся пути между вершинами <math>A_k</math> и <math>A_l</math>, т.е. <math>(A_k, A_l)</math> - не является мостом. Но <math>(A_k, A_l)</math> - мост по условию. Получили противоречие.
<math>T</math> - дерево.
}}
== См. также ==
[[Граф блоков-точек сочленения]]
