Изменения

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

<div class="tleft" style="clear:none">[[Файл:block_cut_vertex_1.png|thumb|250px|Граф <tex>G</tex>]]</div><div class="tleft" style="clear:none">[[Файл:Граф_блоковblock_cut_vertex_2.png|thumb|135px|Граф <tex>T</tex>]]</div>

В определении, приведенном выше, <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> {{--- }} точка сочленения.

== См. также ==