Граф блоков-точек сочленения — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Пусть [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл|граф]] <tex>G</tex> [[Отношение вершинной двусвязности|вершинно двусвязен]]. Обозначим <tex>A_1...A_n</tex> - блоки, а <tex>a_1...a_m</tex> - [[Точка сочленения, эквивалентные определения|точки сочленения]] <tex>G</tex>.
+
Пусть [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл|граф]] <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>.
 
Построим двудольный граф <tex>T</tex>, поместив <tex>A_1...A_n</tex> и <tex>a_1...a_m</tex> в различные его доли. Если точка сочленения принадлежит блоку, проведем между ними ребро. Полученный граф <tex>T</tex> называют '''графом блоков-точек сочленения''' графа <tex>G</tex>.
 
}}
 
}}

Версия 12:26, 23 января 2011

Определение:
Пусть граф [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].


Лемма:
В определениях, приведенных выше, [math]T[/math] - дерево.
Доказательство:
[math]\triangleright[/math]

Достаточно показать, что в [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].
[math]\triangleleft[/math]

См. также