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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
Строка 11: Строка 11:
 
|proof=
 
|proof=
  
''а)'' <tex>T</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> нет циклов.
 
Пусть какие-то две смежные вершины <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> {{---}} дерево.
 
}}
 
}}
  
==Литература==
+
== См. также ==
 +
[[Граф блоков-точек сочленения]]
  
 +
== Источники информации ==
  
== См. также ==
 
[[Граф блоков-точек сочленения]]
 
  
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Связность в графах]]
 
[[Категория:Связность в графах]]

Версия 22:44, 27 января 2016

Определение:
Пусть граф [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]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]

См. также

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

Источники информации