Изменения

Перейти к: навигация, поиск

Граф компонент рёберной двусвязности

126 байт добавлено, 00:10, 14 октября 2010
Нет описания правки
В определениях, приведенных выше, <tex>T</tex> - [[Дерево, эквивалентные определения|дерево]].
|proof=
 
<tex>\land</tex> - пересечение путей.
<tex>A \land B : (a, b) \in A \land B \Rightarrow (a, b) \in A \land (a, b) \in B</tex>
''а)'' <tex>T</tex> - связно. (Следует из определения)
''б)'' В <tex>T</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> - мост по условию. Получили противоречие.
Анонимный участник

Навигация