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