Граф компонент рёберной двусвязности — различия между версиями
| Строка 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
Компоненты реберной двусвязности
| Определение: |
| Компонентами реберной двусвязности графа, называют его подграфы, множества вершин которых - классы эквивалентности реберной двусвязности, а множества ребер - множества ребер из соответствующих классов эквивалентности. |
| Определение: |
| Пусть граф реберно двусвязен. Обозначим - компоненты реберной двусвязности, а - мосты . Построим граф , в котором вершинами будут , а ребрами , соединяющими соответствующие вершины из соответствующих компонент реберной двусвязности. Полученный граф называют графом компонент реберной двусвязности графа . |
