Изменения

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

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

372 байта убрано, 13:53, 31 октября 2011
Нет описания правки
Достаточно показать, что в <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> - точка сочленения.
Пусть аналогично <tex>a_i, A_k, a_j: a_i, a_j \in A_k</tex> - лежащие на цикле последовательные вершины <tex>T</tex>. В этом случае рассуждение такое же, и <tex>a_i</tex> и <tex>a_j</tex> не смогут быть точками сочленения из-за цикла в <tex>G</tex>.
}}
==Литература==
33
правки

Навигация