322
правки
Изменения
первая (сырая) версия статьи
{{Определение
|definition=
Пусть граф <math>G</math> [[Отношение реберной двусвязности|реберно двусвязен]]. Обозначим <math>A_1...A_n</math> - блоки, а <math>a_1...a_m</math> - [[Точка сочленения, эквивалентные определения|точки сочленения]] <math>G</math>.
Построим двудольный граф <math>T</math>, поместив <math>A_1...A_n</math> и <math>a_1...a_m</math> в различные его доли. Если точка сочленения принадлежит блоку, проведем между ними ребро. Полученный граф <math>T</math> называют '''графом блоков-точек сочленения''' графа <math>G</math>.
}}
{{Лемма
|statement=
В определениях, приведенных выше, <math>T</math> - дерево.
|proof=
Достаточно показать, что в <math>T</math> нет циклов.
Пусть <math>A_i, a_k, A_j: a_k \in A_i, A_j</math> - последовательные вершины <math>T</math> и пусть они лежат на цикле. Тогда существует последовательность точек сочленения и блоков, соединяющая <math>A_i</math> и <math>A_j</math> и не содержащая <math>a_k</math>. По ней можно проложить путь в <math>G</math> (можем переходить из блока в блок по точке сочленения и из одной части блока в другую) и замкнуть его в вершине <math>a_k</math>, получив цикл, что противоречит тому, что <math>a_k</math> - точка сочленения.
Пусть аналогично <math>a_i, A_k, a_j: a_i, a_j \in A_k</math> - лежащая на цикле последовательные вершины <math>T</math>. В этом случае рассуждение такое же, и <math>a_i</math> и <math>a_j</math> не смогут быть точками сочленения из-за цикла в <math>G</math>.
}}
См. также [[Граф компонент реберной двусвязности]]
|definition=
Пусть граф <math>G</math> [[Отношение реберной двусвязности|реберно двусвязен]]. Обозначим <math>A_1...A_n</math> - блоки, а <math>a_1...a_m</math> - [[Точка сочленения, эквивалентные определения|точки сочленения]] <math>G</math>.
Построим двудольный граф <math>T</math>, поместив <math>A_1...A_n</math> и <math>a_1...a_m</math> в различные его доли. Если точка сочленения принадлежит блоку, проведем между ними ребро. Полученный граф <math>T</math> называют '''графом блоков-точек сочленения''' графа <math>G</math>.
}}
{{Лемма
|statement=
В определениях, приведенных выше, <math>T</math> - дерево.
|proof=
Достаточно показать, что в <math>T</math> нет циклов.
Пусть <math>A_i, a_k, A_j: a_k \in A_i, A_j</math> - последовательные вершины <math>T</math> и пусть они лежат на цикле. Тогда существует последовательность точек сочленения и блоков, соединяющая <math>A_i</math> и <math>A_j</math> и не содержащая <math>a_k</math>. По ней можно проложить путь в <math>G</math> (можем переходить из блока в блок по точке сочленения и из одной части блока в другую) и замкнуть его в вершине <math>a_k</math>, получив цикл, что противоречит тому, что <math>a_k</math> - точка сочленения.
Пусть аналогично <math>a_i, A_k, a_j: a_i, a_j \in A_k</math> - лежащая на цикле последовательные вершины <math>T</math>. В этом случае рассуждение такое же, и <math>a_i</math> и <math>a_j</math> не смогут быть точками сочленения из-за цикла в <math>G</math>.
}}
См. также [[Граф компонент реберной двусвязности]]
