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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показаны 32 промежуточные версии 8 участников)
Строка 1: Строка 1:
−
== Компоненты реберной двусвязности ==
 
−
 
 
{{Определение
 
{{Определение
−
|definition =
+
|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> {{---}} дерево.
−
 
+
}}
  
 
== См. также ==
 
== См. также ==
 +
* [[Граф блоков-точек сочленения]]
  
−
 
+
[[Категория:Алгоритмы и структуры данных]]
−
[[Граф блоков-точек сочленения]]
+
[[Категория:Связность в графах]]

Текущая версия на 19:26, 4 сентября 2022

Определение:
Пусть граф [math]G[/math] связен. Обозначим [math]A_1\ldots A_n[/math] — компоненты рёберной двусвязности, а [math]a_1\ldots a_m[/math] — мосты [math]G[/math]. Построим граф [math]T[/math], в котором вершинами будут [math]A_1\ldots A_n[/math], а рёбрами — [math]a_1\ldots a_m[/math], соединяющими соответствующие вершины из соответствующих компонент рёберной двусвязности. Полученный граф [math]T[/math] называют графом компонент рёберной двусвязности (англ. costal doubly-linked components graph) графа [math]G[/math].
Граф [math]G[/math]
Граф [math]T[/math]
Лемма:
В определении, приведенном выше, [math]T[/math] — дерево.
Доказательство:
[math]\triangleright[/math]
  1. [math]T[/math] — связно. (Следует из определения)
  2. В [math]T[/math] нет циклов. (Пусть какие-то две смежные вершины [math]A_k[/math] и [math]A_l[/math] принадлежат какому-то циклу. Тогда ребро [math](A_k, A_l)[/math] принадлежит этому же циклу. Следовательно, существуют два рёберно-непересекающихся пути между вершинами [math]A_k[/math] и [math]A_l[/math], т.е. [math](A_k, A_l)[/math] — не является мостом. Но [math](A_k, A_l)[/math] — мост по условию. Получили противоречие)
Из этого следует, что [math]T[/math] — дерево.
[math]\triangleleft[/math]

См. также

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Граф_компонент_рёберной_двусвязности&oldid=85205»