1632
правки
Изменения
м
rollbackEdits.php mass rollback
{{Определение|definition=Пусть [[Основные определения теории графов|граф]] <tex>G</tex> связен. Обозначим <tex>A_1\ldots A_n</tex> {{---}} компоненты рёберной двусвязности, а <tex>a_1\ldots a_m</tex> {{---}} [[Мост, эквивалентные определения|мосты]] <tex>G</tex>.Построим граф <tex>T</tex>, в котором вершинами будут <tex>A_1\ldots A_n</tex>, а рёбрами {{---}} <tex>a_1\ldots a_m</tex>, соединяющими соответствующие вершины из соответствующих компонент рёберной двусвязности. Полученный граф <tex>T</tex> называют '''графом компонент [[Отношение рёберной двусвязности|рёберной двусвязности]]''' ''(англ. costal doubly-linked components graph)'' графа <tex>G</tex>.}}<div class="tleft" style="clear:none">[[Файл:Double_edge_1.png|thumb|240px|Граф <tex>G</tex>]]</div><div class="tleft" style= Компоненты реберной двусвязности "clear:none">[[Файл:Double_edge_2.png|thumb|175px|Граф <tex>T</tex>]]</div>{{Лемма|statement=В определении, приведенном выше, <tex>T</tex> {{---}} [[Дерево, эквивалентные определения|дерево]].|proof=
#<tex>T</tex> {{Определение---}} связно. (Следует из определения)|definition =Компонентами реберной двусвязности графа#В <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> {{-- множества ребер из соответствующих классов эквивалентности-}} дерево.
}}
== См. также ==
* [[Граф блоков-точек сочленения]]
[[Категория:Алгоритмы и структуры данных]]
[[Категория:Связность в графах]]
