Изменения

Пусть [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл|граф ]] <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> называют '''графом блоков-точек сочленения''' ''(англ. block cutpoint graph)'' графа <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_kA_i</mathtex> - точка сочленения.Пусть аналогично и <mathtex>a_i, A_k, a_j: a_i, a_j \in A_kA_j</mathtex> - лежащая на цикле последовательные вершины <math>T</math>. В этом случае рассуждение такое принадлежат одному и тому жециклу, что противоречит тому, и <math>a_i</math> и <math>a_j</math> не смогут быть точками сочленения из-за цикла что они находятся в <math>G</math>разных блоках.

См==Источники информации==* Асанов М. также О., Баранский В. А., Расин В. В. '''Дискретная математика: графы, матроиды, алгоритмы''' — НИЦ РХД, 2001. — 288 с. — ISBN 5-93972-076-5 [[Категория:Алгоритмы и структуры данных]][[Граф компонент реберной двусвязностиКатегория:Связность в графах]]