Просмотр исходного текста страницы Граф блоков-точек сочленения

{{Определение
|definition=
Пусть [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл|граф]] <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> называют '''графом блоков-точек сочленения''' графа <tex>G</tex>.
}}
[[Файл:Граф_блоков.png]]
<br>
{{Лемма
|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> - точка сочленения.
Пусть аналогично <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>.
}}
==Литература==


== См. также ==
* [[Граф компонент реберной двусвязности]]