Изменения

Пусть [[Основные определения теории графов|граф ]] <mathtex>G</mathtex> [[Отношение реберной двусвязности|реберно двусвязен]]связен. Обозначим <mathtex>A_1...\ldots A_n</mathtex> {{- --}} компоненты реберной рёберной двусвязности, а <mathtex>a_1...\ldots a_m</mathtex> {{- --}} [[Мост, эквивалентные определения|мосты]] <mathtex>G</mathtex>.Построим граф <mathtex>T</mathtex>, в котором вершинами будут <mathtex>A_1...\ldots A_n</mathtex>, а ребрами рёбрами {{---}} <mathtex>a_1...\ldots a_m</mathtex>, соединяющими соответствующие вершины из соответствующих компонент реберной рёберной двусвязности. Полученный граф <mathtex>T</mathtex> называют '''графом компонент реберной [[Отношение рёберной двусвязности|рёберной двусвязности]]''' ''(англ. costal doubly-linked components graph)'' графа <mathtex>G</mathtex>.

В определенияхопределении, приведенных приведенном выше, <mathtex>T</mathtex> {{- --}} [[Дерево, эквивалентные определения|дерево]].

Следовательно, #<tex>T</tex> {{---}} связно. (Следует из определения)#В <tex>T</tex> нет циклов. (Пусть какие-то две смежные вершины <tex>A_k</tex> и <tex>A_l</tex> принадлежат какому-то циклу. Тогда ребро <mathtex>\exist(A_k, A_l)</mathtex> принадлежит этому же циклу. Следовательно, существуют два реберно не пересекающихся рёберно-непересекающихся пути между вершинами <mathtex>A_k</mathtex> и <mathtex>A_l</mathtex>, т.е. <mathtex>(A_k, A_l)</mathtex> {{--- }} не является мостом. Но <mathtex>(A_k, A_l)</mathtex> {{--- }} мост по условию. Получили противоречие.):Из этого следует, что <mathtex>T</mathtex> {{--- }} дерево.

* [[Граф блоков-точек сочленения]] [[Категория:Алгоритмы и структуры данных]][[Категория:Связность в графах]]