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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 4: Строка 4:
 
Построим граф <tex>T</tex>, в котором вершинами будут <tex>A_1\ldots A_n</tex>, а ребрами {{---}} <tex>a_1\ldots a_m</tex>, соединяющими соответствующие вершины из соответствующих компонент реберной двусвязности. Полученный граф <tex>T</tex> называют '''графом компонент [[Отношение реберной двусвязности|реберной двусвязности]]''' графа <tex>G</tex>.
 
Построим граф <tex>T</tex>, в котором вершинами будут <tex>A_1\ldots A_n</tex>, а ребрами {{---}} <tex>a_1\ldots a_m</tex>, соединяющими соответствующие вершины из соответствующих компонент реберной двусвязности. Полученный граф <tex>T</tex> называют '''графом компонент [[Отношение реберной двусвязности|реберной двусвязности]]''' графа <tex>G</tex>.
 
}}
 
}}
[[Файл:Граф компонент.jpg]]
+
[[Файл:Граф_компонент.png|200px|thumb|left|описание]]
 
{{Лемма
 
{{Лемма
 
|statement=
 
|statement=

Версия 07:55, 25 октября 2011

Определение:
Пусть граф [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] называют графом компонент реберной двусвязности графа [math]G[/math].
описание
Лемма:
В определении, приведенном выше, [math]T[/math]дерево.
Доказательство:
[math]\triangleright[/math]

а) [math]T[/math] — связно. (Следует из определения)

б) В [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]

См. также

Граф блоков-точек сочленения