Материал из Викиконспекты
| Определение: |
| Пусть граф [math]G[/math] связен. Обозначим [math]A_1\ldots A_n[/math] — компоненты реберной двусвязности, а [math]a_1\ldots a_m[/math] — мосты [math]G[/math].
Построим граф [math]T[/math], в котором вершинами будут [math]A_1\ldots A_n[/math], а ребрами — [math]a_1\ldots a_m[/math], соединяющими соответствующие вершины из соответствующих компонент реберной двусвязности. Полученный граф [math]T[/math] называют графом компонент реберной двусвязности (англ. costal doubly-linked components graph) графа [math]G[/math]. |
| Лемма: |
В определении, приведенном выше, [math]T[/math] — дерево. |
| Доказательство: |
| [math]\triangleright[/math] |
- [math]T[/math] — связно. (Следует из определения)
- В [math]T[/math] нет циклов. (Пусть какие-то две смежные вершины [math]A_k[/math] и [math]A_l[/math] принадлежат какому-то циклу. Тогда ребро [math](A_k, A_l)[/math] принадлежит этому же циклу. Следовательно, существуют два реберно-непересекающихся пути между вершинами [math]A_k[/math] и [math]A_l[/math], т.е. [math](A_k, A_l)[/math] — не является мостом. Но [math](A_k, A_l)[/math] — мост по условию. Получили противоречие)
- Из этого следует, что [math]T[/math] — дерево.
|
| [math]\triangleleft[/math] |
См. также
