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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
Строка 15: Строка 15:
 
Пусть <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_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> {{---}} точка сочленения.
 
}}
 
}}
==Литература==
 
М.О.Асанов, В.А.Баранский, В.В.Расин
 
ДИСКРЕТНАЯ МАТЕМАТИКА: ГРАФЫ, МАТРОИДЫ, АЛГОРИТМЫ
 
  
== См. также ==
+
==См. также==
 
* [[Граф компонент реберной двусвязности]]
 
* [[Граф компонент реберной двусвязности]]
 +
 +
==Источники информации==
 +
* Асанов М. О., Баранский В. А., Расин В. В. '''Дискретная математика: графы, матроиды, алгоритмы''' — НИЦ РХД, 2001. — 288 с. — ISBN 5-93972-076-5
  
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Связность в графах]]
 
[[Категория:Связность в графах]]

Версия 22:50, 27 января 2016

Определение:
Пусть граф [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]G[/math]
Граф [math]T[/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]\triangleleft[/math]

См. также

Источники информации

  • Асанов М. О., Баранский В. А., Расин В. В. Дискретная математика: графы, матроиды, алгоритмы — НИЦ РХД, 2001. — 288 с. — ISBN 5-93972-076-5