Деревья Эйлерова обхода — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Реализация структуры)
(Операции c эйлеровыми обходами)
Строка 37: Строка 37:
 
==Операции c эйлеровыми обходами==
 
==Операции c эйлеровыми обходами==
 
Представление деревьев в виде их эйлеровых обходов позволяет свести задачу о динамической связности к следующим операциям с последовательностями вершин:
 
Представление деревьев в виде их эйлеровых обходов позволяет свести задачу о динамической связности к следующим операциям с последовательностями вершин:
 
===Изменение корня дерева (переподвешивание)===
 
Дано дерево с корнем в вершине <tex>a</tex>. Требуется переподвесить его к вершине <tex>h</tex>.
 
 
[[Файл:Tour14.png |thumb|320px|center]]
 
 
Для переподвешивания (англ. ''rerooting'') необходимо:
 
*Разбить эйлеров обход на три части:
 
*: <tex>S1</tex> - вершины, посещенные эйлеровым обходом до захода в <tex>h</tex>.
 
*: <tex>H</tex> - вершины между первым и последним вхождением нового корня <tex>h</tex>.
 
*: <tex>S2 </tex> - вершины, посещенные эйлеровым обходом после выхода из <tex>h</tex>.
 
*Удалить первую вершину в <tex>S1 </tex>.
 
*Соединить в следующем порядке: <tex>H</tex>, <tex>S2 </tex>, <tex>S1 </tex>.
 
*Добавить <tex>\{h\}</tex> в конец последовательности.
 
 
[[Файл:Tour13.png |thumb|320px|center]]
 
 
В результате получим:
 
 
[[Файл:Proba.png |center]]
 
  
 
===Добавление ребра===
 
===Добавление ребра===
Строка 62: Строка 42:
 
[[Файл:Link11.png |thumb|400px|center]]
 
[[Файл:Link11.png |thumb|400px|center]]
  
Для связывания деревьев <tex>T1 </tex> и <tex>T2</tex>, где <tex>c\in T1\ </tex>, а <tex>g\in T2\</tex> добавлением ребра <tex>\{c, g\} \</tex> необходимо:
+
Пусть хотим добавить ребро <tex>\{c, g\} \</tex>
*Переподвесить дерево <tex>T1</tex> к вершине <tex>c</tex>, если корнем дерева была другая вершина.
+
Выберем любое вхождение вершины <tex>с</tex> в эйлеров обход T1
*Переподвесить дерево <tex>T2</tex> к вершине <tex>g</tex>, если корнем дерева была другая вершина.
+
Разрежем эйлеров обход T1 на 2 части
*Соединить получившиеся эйлеровы обходы.
+
A1 - часть обхода до выбранного вхождения вершины <tex>с</tex>
*Добавить <tex>\{c\}</tex> в конец последовательности.
+
A2 - часть обхода после выбранного вхождения вершины <tex>с</tex>
 
+
Аналогично, выберем любое вхождение вершины <tex>g</tex> в эйлеров обход T2 и разрежем его на 2 части B1 и B2
[[Файл:Link2.png|thumb|400px |center]]
+
Соберем результирующий эйлеров обход в порядке A1 B2 B1 A2
 
 
В результате получим эйлеров обход дерева с корнем в вершине <tex>c</tex>:
 
  
[[Файл:Link3.png|center]]
+
Чтобы быстро находить место, где разрезать эйлеровы обходы T1 и T2, будем хранить эйлеровы обходы в двоичных деревьях поиска.
 +
Ключом вершины, для построения дерева поиска, будет время посещения этой вершины эйлеровым обходом.
 +
Для каждой вершины дерева (T1, T2) будем хранить указатель на вершину в дереве поиска, которая соответствует вхождению вершины дерева в эйлеров обход.
 +
Тогда за O(1) переходим от вершины дерева к вершине дерева поиска, по которой за O(log n) можно будет разделить дерево поиска на 2 части.  
  
 
===Разрезание ребра===
 
===Разрезание ребра===

Версия 00:45, 31 декабря 2016

Задача о динамической связности

Задача:
Для динамически изменяющегося дерева выполнить следующие запросы:
  • [math]\mathrm{link(u, w)}[/math] — добавить ребро [math](u, w)[/math] (при условии, что вершины [math]u[/math] и [math]w[/math] принадлежат разным деревьям),
  • [math]\mathrm{cut(u, w)}[/math] — разрезать ребро [math](u, w)[/math] (при условии, что ребро [math](u, w)[/math] принадлежит дереву),
  • [math]\mathrm{isConnected(u, w)}[/math] — определить принадлежат ли вершины [math]u[/math] и [math]w[/math] одной компоненте связности.


Для решения поставленной задачи будем представлять дерево в виде его эйлерова графа, а затем будем работать с эйлеровым обходом (англ.Euler tour tree) этого графа. Это позволит выполнять указанные запросы за [math]O(\log n)[/math].

Представление деревьев в виде эйлерова графа

Пример дерева
Соответствующий эйлеров граф

Для представления дерева в виде эйлерового графа заменим каждое ребро [math]\{u, v\} \[/math] дерева на два ребра [math](u, v)[/math] и [math](v, u)[/math].

Получившийся ориентированный граф будет эйлеровым согласно критерию.







Представим дерево с корнем в вершине [math]a[/math] в виде последовательности вершин, посещеннных в порядке эйлерова обхода.

Tour1.png
Утверждение:
Последовательность вершин между первым и последним вхождениями вершины [math]h[/math] в эйлеров обход дерева, представляет эйлеров обход поддерва с корнем в [math]h[/math].
[math]\triangleright[/math]

Действительно, при обходе дерева последний раз выйдем из вершины, только после посещения всех вершин ее поддерева.

Tour2.png
[math]\triangleleft[/math]

Операции c эйлеровыми обходами

Представление деревьев в виде их эйлеровых обходов позволяет свести задачу о динамической связности к следующим операциям с последовательностями вершин:

Добавление ребра

Link11.png

Пусть хотим добавить ребро [math]\{c, g\} \[/math] Выберем любое вхождение вершины [math]с[/math] в эйлеров обход T1 Разрежем эйлеров обход T1 на 2 части A1 - часть обхода до выбранного вхождения вершины [math]с[/math] A2 - часть обхода после выбранного вхождения вершины [math]с[/math] Аналогично, выберем любое вхождение вершины [math]g[/math] в эйлеров обход T2 и разрежем его на 2 части B1 и B2 Соберем результирующий эйлеров обход в порядке A1 B2 B1 A2

Чтобы быстро находить место, где разрезать эйлеровы обходы T1 и T2, будем хранить эйлеровы обходы в двоичных деревьях поиска. Ключом вершины, для построения дерева поиска, будет время посещения этой вершины эйлеровым обходом. Для каждой вершины дерева (T1, T2) будем хранить указатель на вершину в дереве поиска, которая соответствует вхождению вершины дерева в эйлеров обход. Тогда за O(1) переходим от вершины дерева к вершине дерева поиска, по которой за O(log n) можно будет разделить дерево поиска на 2 части.

Разрезание ребра

Cut1.png

Для разбиения дерева на два поддерева путем разрезания ребра [math]\{g, j\} \[/math] необходимо:

  • Переподвесить дерево к вершине [math]g[/math].
  • Разделить дерево на части [math]E1, V, E2[/math], где [math]V[/math] отрезок между первым и последним вхождением вершины [math]j[/math].
  • Эйлеров обход первого поддерева образуется соединением [math]E1[/math] и [math]E2[/math], с удалением повторного [math]\{g\}[/math] в месте их соединения.
  • Эйлеров обход второго поддерева образует [math]V[/math].
Cut2.png

В результате получим:

Cut3.png

Реализация структуры

Представим последовательность вершин эйлерова обхода в виде сбалансированного двоичного дерева. Будем использовать красно-черное дерево.

Balanced tree.png

Объединение и разделение красно-черных деревьев выполняется за [math]O(\log n)[/math][1].

Для каждой вершины храним указатели на её первое и последнее вхождение в последовательность. Значит, имеем доступ к ним за [math]O(1)[/math].

Запрос о принадлежности вершин к одной компоненте связности выполняется за [math]O(\log n)[/math] проверкой лежат ли эти вершины в одном дереве.

Balanced tree1.png

См. также

Примечания

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