Изменения

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

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

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

Навигация