Изменения

Пусть [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл|граф ]] <mathtex>G</mathtex> [[Отношение вершинной двусвязности|вершинно двусвязен]]. Обозначим <mathtex>A_1...A_n</mathtex> - блоки, а <mathtex>a_1...a_m</mathtex> - [[Точка сочленения, эквивалентные определения|точки сочленения]] <mathtex>G</mathtex>.Построим двудольный граф <mathtex>T</mathtex>, поместив <mathtex>A_1...A_n</mathtex> и <mathtex>a_1...a_m</mathtex> в различные его доли. Если точка сочленения принадлежит блоку, проведем между ними ребро. Полученный граф <mathtex>T</mathtex> называют '''графом блоков-точек сочленения''' графа <mathtex>G</mathtex>.

В определениях, приведенных выше, <mathtex>T</mathtex> - дерево.

Достаточно показать, что в <mathtex>T</mathtex> нет циклов.Пусть <mathtex>A_i, a_k, A_j: a_k \in A_i, A_j</mathtex> - последовательные вершины <mathtex>T</mathtex>, лежащие на цикле. Тогда существует последовательность точек сочленения и блоков, соединяющая <mathtex>A_i</mathtex> и <mathtex>A_j</mathtex> и не содержащая <mathtex>a_k</mathtex>. По ней можно проложить путь в <mathtex>G</mathtex> (можем переходить из блока в блок по точке сочленения и из одной части блока в другую) и замкнуть его в вершине <mathtex>a_k</mathtex>, получив цикл, что противоречит тому, что <mathtex>a_k</mathtex> - точка сочленения.Пусть аналогично <mathtex>a_i, A_k, a_j: a_i, a_j \in A_k</mathtex> - лежащая на цикле последовательные вершины <mathtex>T</mathtex>. В этом случае рассуждение такое же, и <mathtex>a_i</mathtex> и <mathtex>a_j</mathtex> не смогут быть точками сочленения из-за цикла в <mathtex>G</mathtex>.