Граф блоков-точек сочленения — различия между версиями
Proshev (обсуждение | вклад) |
м (rollbackEdits.php mass rollback) |
||
| (не показано 9 промежуточных версий 5 участников) | |||
| Строка 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> называют '''графом блоков-точек сочленения''' ''(англ. block cutpoint graph)'' графа <tex>G</tex>. |
}} | }} | ||
| − | [[Файл: | + | <div class="tleft" style="clear:none">[[Файл:block_cut_vertex_1.png|thumb|250px|Граф <tex>G</tex>]]</div> |
| + | <div class="tleft" style="clear:none">[[Файл:block_cut_vertex_2.png|thumb|135px|Граф <tex>T</tex>]]</div> | ||
<br> | <br> | ||
{{Лемма | {{Лемма | ||
|id=lemma1 | |id=lemma1 | ||
|statement= | |statement= | ||
| − | В определении, приведенном выше, <tex>T</tex> - дерево. | + | В определении, приведенном выше, <tex>T</tex> {{---}} [[Дерево, эквивалентные определения|дерево]]. |
|proof= | |proof= | ||
Достаточно показать, что в <tex>T</tex> нет циклов. | Достаточно показать, что в <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_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_i</tex> и <tex>A_j</tex> принадлежат одному и тому же циклу, что противоречит тому, что они находятся в разных блоках. |
}} | }} | ||
| − | |||
| − | |||
| − | |||
| − | == См. также == | + | ==См. также== |
* [[Граф компонент реберной двусвязности]] | * [[Граф компонент реберной двусвязности]] | ||
| + | |||
| + | ==Источники информации== | ||
| + | * Асанов М. О., Баранский В. А., Расин В. В. '''Дискретная математика: графы, матроиды, алгоритмы''' — НИЦ РХД, 2001. — 288 с. — ISBN 5-93972-076-5 | ||
[[Категория:Алгоритмы и структуры данных]] | [[Категория:Алгоритмы и структуры данных]] | ||
[[Категория:Связность в графах]] | [[Категория:Связность в графах]] | ||
Текущая версия на 19:33, 4 сентября 2022
| Определение: |
| Пусть граф связен. Обозначим — блоки, а — точки сочленения . Построим двудольный граф , поместив и в различные его доли. Если точка сочленения принадлежит блоку, проведем между ними ребро. Полученный граф называют графом блоков-точек сочленения (англ. block cutpoint graph) графа . |
| Лемма: |
В определении, приведенном выше, — дерево. |
| Доказательство: |
|
Достаточно показать, что в нет циклов. Пусть — последовательные вершины , лежащие на цикле. Тогда существует последовательность точек сочленения и блоков, соединяющая и и не содержащая . По ней можно проложить путь в (можем переходить из блока в блок по точке сочленения и из одной части блока в другую) и замкнуть его в вершине , получив цикл. Получается, что некоторые рёбра из и принадлежат одному и тому же циклу, что противоречит тому, что они находятся в разных блоках. |
См. также
Источники информации
- Асанов М. О., Баранский В. А., Расин В. В. Дискретная математика: графы, матроиды, алгоритмы — НИЦ РХД, 2001. — 288 с. — ISBN 5-93972-076-5
