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

Материал из Викиконспекты
Перейти к: навигация, поиск

Компоненты реберной двусвязности

Определение:
Компонентами реберной двусвязности графа, называют его подграфы, множества вершин которых - классы эквивалентности реберной двусвязности, а множества ребер - множества ребер из соответствующих классов эквивалентности.


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

См. также