Граф компонент рёберной двусвязности — различия между версиями
Proshev (обсуждение | вклад) |
м (rollbackEdits.php mass rollback) |
||
| (не показано 9 промежуточных версий 4 участников) | |||
| Строка 1: | Строка 1: | ||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
| − | Пусть [[Основные определения теории графов|граф]] <tex>G</tex> связен. Обозначим <tex>A_1\ldots A_n</tex> {{---}} компоненты | + | Пусть [[Основные определения теории графов|граф]] <tex>G</tex> связен. Обозначим <tex>A_1\ldots A_n</tex> {{---}} компоненты рёберной двусвязности, а <tex>a_1\ldots a_m</tex> {{---}} [[Мост, эквивалентные определения|мосты]] <tex>G</tex>. |
| − | Построим граф <tex>T</tex>, в котором вершинами будут <tex>A_1\ldots A_n</tex>, а | + | Построим граф <tex>T</tex>, в котором вершинами будут <tex>A_1\ldots A_n</tex>, а рёбрами {{---}} <tex>a_1\ldots a_m</tex>, соединяющими соответствующие вершины из соответствующих компонент рёберной двусвязности. Полученный граф <tex>T</tex> называют '''графом компонент [[Отношение рёберной двусвязности|рёберной двусвязности]]''' ''(англ. costal doubly-linked components graph)'' графа <tex>G</tex>. |
}} | }} | ||
| − | [[Файл: | + | <div class="tleft" style="clear:none">[[Файл:Double_edge_1.png|thumb|240px|Граф <tex>G</tex>]]</div> |
| + | <div class="tleft" style="clear:none">[[Файл:Double_edge_2.png|thumb|175px|Граф <tex>T</tex>]]</div> | ||
{{Лемма | {{Лемма | ||
|statement= | |statement= | ||
| Строка 10: | Строка 11: | ||
|proof= | |proof= | ||
| − | + | #<tex>T</tex> {{---}} связно. (Следует из определения) | |
| − | + | #В <tex>T</tex> нет циклов. (Пусть какие-то две смежные вершины <tex>A_k</tex> и <tex>A_l</tex> принадлежат какому-то циклу. Тогда ребро <tex>(A_k, A_l)</tex> принадлежит этому же циклу. Следовательно, существуют два рёберно-непересекающихся пути между вершинами <tex>A_k</tex> и <tex>A_l</tex>, т.е. <tex>(A_k, A_l)</tex> {{---}} не является мостом. Но <tex>(A_k, A_l)</tex> {{---}} мост по условию. Получили противоречие) | |
| − | + | :Из этого следует, что <tex>T</tex> {{---}} дерево. | |
| − | Пусть какие-то две смежные вершины <tex>A_k</tex> и <tex>A_l</tex> принадлежат какому-то циклу. Тогда ребро <tex>(A_k, A_l)</tex> принадлежит этому же циклу. | ||
| − | |||
| − | Следовательно, существуют два | ||
| − | <tex>T</tex> {{---}} дерево. | ||
}} | }} | ||
| − | |||
| − | |||
| − | |||
== См. также == | == См. также == | ||
| − | [[Граф блоков-точек сочленения]] | + | * [[Граф блоков-точек сочленения]] |
[[Категория:Алгоритмы и структуры данных]] | [[Категория:Алгоритмы и структуры данных]] | ||
[[Категория:Связность в графах]] | [[Категория:Связность в графах]] | ||
Текущая версия на 19:26, 4 сентября 2022
| Определение: |
| Пусть граф связен. Обозначим — компоненты рёберной двусвязности, а — мосты . Построим граф , в котором вершинами будут , а рёбрами — , соединяющими соответствующие вершины из соответствующих компонент рёберной двусвязности. Полученный граф называют графом компонент рёберной двусвязности (англ. costal doubly-linked components graph) графа . |
| Лемма: |
В определении, приведенном выше, — дерево. |
| Доказательство: |
|
