Изменения

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

Граф блоков-точек сочленения

881 байт убрано, 20:07, 24 мая 2020
Через точки сочленения могут проходить циклы. Доказательство неверное.
|id=lemma1
|statement=
В определении, приведенном выше, <tex>T</tex> {{---}} [[Дерево, эквивалентные определения|дерево]].|proof=Достаточно показать, что в <tex>T</tex> нет циклов.Пусть <tex>A_i, a_k, A_j: a_k \in A_i, A_j</tex> {{---}} последовательные вершины <tex>T</tex>, лежащие на цикле. Тогда существует последовательность точек сочленения и блоков, соединяющая <tex>A_i</tex> и <tex>A_j</tex> и не содержащая <tex>a_k</tex>. По ней можно проложить путь в <tex>G</tex> (можем переходить из блока в блок по точке сочленения и из одной части блока в другую) и замкнуть его в вершине <tex>a_k</tex>, получив цикл, что противоречит тому, что <tex>a_k</tex> {{---}} точка сочленения.}}
==См. также==
3
правки

Навигация