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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 6: Строка 6:
 
}}
 
}}
  
 
+
{{Определение
 
+
|definition=
 
+
Пусть граф <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>.
 
+
}}
 
== См. также ==
 
== См. также ==
 
 
 
[[Граф блоков-точек сочленения]]
 
[[Граф блоков-точек сочленения]]

Версия 06:12, 7 октября 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].

См. также

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