Редактирование: Граф компонент рёберной двусвязности

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Пусть [[Основные определения теории графов|граф]] <tex>G</tex> связен. Обозначим <tex>A_1\ldots A_n</tex> {{---}} компоненты рёберной двусвязности, а <tex>a_1\ldots 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\ldots A_n</tex>, а рёбрами {{---}} <tex>a_1\ldots a_m</tex>, соединяющими соответствующие вершины из соответствующих компонент рёберной двусвязности. Полученный граф <tex>T</tex> называют '''графом компонент [[Отношение рёберной двусвязности|рёберной двусвязности]]''' ''(англ. costal doubly-linked components graph)'' графа <tex>G</tex>.
+
Построим граф <tex>T</tex>, в котором вершинами будут <tex>A_1...A_n</tex>, а ребрами <tex>a_1...a_m</tex>, соединяющими соответствующие вершины из соответствующих компонент реберной двусвязности. Полученный граф <tex>T</tex> называют '''графом компонент [[Отношение реберной двусвязности|реберной двусвязности]]''' графа <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=
В определении, приведенном выше, <tex>T</tex> {{---}} [[Дерево, эквивалентные определения|дерево]].
+
В определениях, приведенных выше, <tex>T</tex> - [[Дерево, эквивалентные определения|дерево]].
 
|proof=
 
|proof=
  
#<tex>T</tex> {{---}} связно. (Следует из определения)
+
''а)'' <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>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> - дерево.
 
}}
 
}}
 
 
== См. также ==
 
== См. также ==
* [[Граф блоков-точек сочленения]]
+
[[Граф блоков-точек сочленения]]
 
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Связность в графах]]
 

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: