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