Изменения

Пусть [[Основные определения теории графов|граф ]] <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> {{- --}} [[Дерево, эквивалентные определения|дерево]].

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

''б)'' В <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> - дерево.}}== См. также ==структуры данных]][[Граф блоков-точек сочлененияКатегория:Связность в графах]]