Отношение рёберной двусвязности
Версия от 16:52, 15 сентября 2015; 5.18.163.31 (обсуждение)
Реберная двусвязность
Определение: |
Две вершины графа называются реберно двусвязными (edge biconnected), если между этими вершинами существуют два реберно непересекающихся пути. | и
Теорема: |
Отношение реберной двусвязности является отношением эквивалентности на вершинах. |
Доказательство: |
Пусть
Рефлексивность: (Очевидно)Симметричность: (Очевидно)Транзитивность: иДоказательство: Пусть из Рассмотрим два пути в есть два реберно непересекающихся пути, и соответственно. Обозначим за объединение двух реберно непересекающихся путей из в . будет реберно-простым циклом. Пусть вершины и — первые со стороны вершины на пересечении и с соответственно. и , такие, что части и идут в разные стороны по циклу . Наличие двух таких реберно непересекающихся путей очевидно, а значит и реберно двусвязны. | — отношение реберной двусвязности.
Компоненты реберной двусвязности
Определение: |
Компонентами реберной двусвязности (costal doubly-linked components) графа называют его подграфы, множества вершин которых - классы эквивалентности реберной двусвязности, а множества ребер - множества ребер из соответствующих классов эквивалентности. |
См. также
Источники информации
- Харари Фрэнк Теория графов = Graph theory/Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 60 с. — ISBN 5-354-00301-6
- Визуализатор - компоненты двусвязности