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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
−
Пусть граф <math>G</math> [[Отношение реберной двусвязности|реберно двусвязен]]. Обозначим <math>A_1...A_n</math> - компоненты реберной двусвязности, а <math>a_1...a_m</math> - [[Мост, эквивалентные определения|мосты]] <math>G</math>.
+
Пусть граф <tex>G</tex> [[Отношение реберной двусвязности|реберно двусвязен]]. Обозначим <tex>A_1...A_n</tex> - компоненты реберной двусвязности, а <tex>a_1...a_m</tex> - [[Мост, эквивалентные определения|мосты]] <tex>G</tex>.
−
Построим граф <math>T</math>, в котором вершинами будут <math>A_1...A_n</math>, а ребрами <math>a_1...a_m</math>, соединяющими соответствующие вершины из соответствующих компонент реберной двусвязности. Полученный граф <math>T</math> называют '''графом компонент реберной двусвязности''' графа <math>G</math>.
+
Построим граф <tex>T</tex>, в котором вершинами будут <tex>A_1...A_n</tex>, а ребрами <tex>a_1...a_m</tex>, соединяющими соответствующие вершины из соответствующих компонент реберной двусвязности. Полученный граф <tex>T</tex> называют '''графом компонент реберной двусвязности''' графа <tex>G</tex>.
 
}}
 
}}
 
{{Лемма
 
{{Лемма
 
|statement=
 
|statement=
−
В определениях, приведенных выше, <math>T</math> - дерево.
+
В определениях, приведенных выше, <tex>T</tex> - дерево.
 
|proof=
 
|proof=
  
−
''а)'' <math>T</math> - связно. (Следует из определения)
+
''а)'' <tex>T</tex> - связно. (Следует из определения)
  
−
''б)'' В <math>T</math> нет циклов.
+
''б)'' В <tex>T</tex> нет циклов.
−
Пусть какие-то две последовательные вершины <math>A_k</math> и <math>A_l</math> принадлежат какому-то циклу. Тогда ребро <math>(A_k,  A_l)</math> принадлежит этому же циклу.
+
Пусть какие-то две последовательные вершины <tex>A_k</tex> и <tex>A_l</tex> принадлежат какому-то циклу. Тогда ребро <tex>(A_k,  A_l)</tex> принадлежит этому же циклу.
  
−
Следовательно, <math>\exist</math> два реберно не пересекающихся пути между вершинами <math>A_k</math>  и <math>A_l</math>, т.е. <math>(A_k, A_l)</math> - не является мостом. Но <math>(A_k, A_l)</math> - мост по условию. Получили противоречие.
+
Следовательно, существуют два реберно не пересекающихся пути между вершинами <tex>A_k</tex>  и <tex>A_l</tex>, т.е. <tex>(A_k, A_l)</tex> - не является мостом. Но <tex>(A_k, A_l)</tex> - мост по условию. Получили противоречие.
−
<math>T</math> - дерево.
+
<tex>T</tex> - дерево.
 
}}
 
}}
 
== См. также ==
 
== См. также ==
 
[[Граф блоков-точек сочленения]]
 
[[Граф блоков-точек сочленения]]

Версия 23:51, 13 октября 2010

Определение:
Пусть граф [math]G[/math] реберно двусвязен. Обозначим [math]A_1...A_n[/math] - компоненты реберной двусвязности, а [math]a_1...a_m[/math] - мосты [math]G[/math]. Построим граф [math]T[/math], в котором вершинами будут [math]A_1...A_n[/math], а ребрами [math]a_1...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]

См. также

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

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