Изменения

Перейти к: навигация, поиск

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

960 байт добавлено, 19:26, 4 сентября 2022
м
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=Пусть граф <mathtex>GT</mathtex> [[Отношение реберной двусвязности|реберно двусвязен]]нет циклов. Обозначим (Пусть какие-то две смежные вершины <mathtex>A_1...A_nA_k</mathtex> - компоненты реберной двусвязности, а и <mathtex>a_1...a_mA_l</mathtex> принадлежат какому- [[Мост, эквивалентные определения|мосты]] то циклу. Тогда ребро <mathtex>G(A_k, A_l)</mathtex>принадлежит этому же циклу.Построим граф Следовательно, существуют два рёберно-непересекающихся пути между вершинами <mathtex>TA_k</mathtex>, в котором вершинами будут и <mathtex>A_1...A_nA_l</mathtex>, а ребрами т.е. <mathtex>a_1...a_m(A_k, A_l)</mathtex>, соединяющими соответствующие вершины из соответствующих компонент реберной двусвязности{{---}} не является мостом. Полученный граф Но <mathtex>T(A_k, A_l)</mathtex> называют '''графом компонент реберной двусвязности''' графа {{---}} мост по условию. Получили противоречие):Из этого следует, что <mathtex>GT</mathtex>{{---}} дерево.
}}
 
== См. также ==
* [[Граф блоков-точек сочленения]] [[Категория:Алгоритмы и структуры данных]][[Категория:Связность в графах]]
1632
правки

Навигация