Граф блоков-точек сочленения — различия между версиями
Maksnov (обсуждение | вклад) |
Maksnov (обсуждение | вклад) |
||
Строка 10: | Строка 10: | ||
|id=lemma1 | |id=lemma1 | ||
|statement= | |statement= | ||
− | В определении, приведенном выше, <tex>T</tex> {{---}} дерево. | + | В определении, приведенном выше, <tex>T</tex> {{---}} [[Дерево, эквивалентные определения|дерево]]. |
|proof= | |proof= | ||
Достаточно показать, что в <tex>T</tex> нет циклов. | Достаточно показать, что в <tex>T</tex> нет циклов. |
Версия 01:00, 28 января 2016
Определение: |
Пусть граф связен. Обозначим — блоки, а — точки сочленения . Построим двудольный граф , поместив и в различные его доли. Если точка сочленения принадлежит блоку, проведем между ними ребро. Полученный граф называют графом блоков-точек сочленения (англ. block cutpoint graph) графа . |
Лемма: |
В определении, приведенном выше, дерево. — |
Доказательство: |
Достаточно показать, что в Пусть нет циклов. — последовательные вершины , лежащие на цикле. Тогда существует последовательность точек сочленения и блоков, соединяющая и и не содержащая . По ней можно проложить путь в (можем переходить из блока в блок по точке сочленения и из одной части блока в другую) и замкнуть его в вершине , получив цикл, что противоречит тому, что — точка сочленения. |
См. также
Источники информации
- Асанов М. О., Баранский В. А., Расин В. В. Дискретная математика: графы, матроиды, алгоритмы — НИЦ РХД, 2001. — 288 с. — ISBN 5-93972-076-5