1632
правки
Изменения
м
rollbackEdits.php mass rollback
==Задача о динамической связности=={{ОпределениеЗадача|definition=Для динамически изменяющегося дерева выполнить следующие запросы:* '''Euler tour tree<tex>\mathrm{link(u, w)}</tex>''' {{---}} добавить ребро <tex>(англ. u, w)</tex> (при условии, что вершины <tex>u</tex> и <tex>w</tex> принадлежат разным деревьям),* ''ETT'<tex>\mathrm{cut(u, w)}</tex>''' {{---}} разрезать ребро <tex>(u, w)</tex> (при условии, что ребро <tex>(u, w) is a method for representing a rooted undirected tree as a number sequence</tex> принадлежит дереву),* '''<tex>\mathrm{isConnected(u, w)}</tex>''' {{---}} определить принадлежат ли вершины <tex>u</tex> и <tex>w</tex> одной компоненте связности.
}}
Для решения поставленной задачи будем представлять дерево в виде его [[Эйлеровость графов|эйлерова графа]], а затем будем работать с [[Эйлеровость графов|эйлеровым обходом]] (англ.''Euler tour tree'') этого графа. Это позволит выполнять указанные запросы за <tex>O(\log n)</tex>.
==Представление деревьев в виде эйлерова графа==
[[Файл:Tree.png|300px|thumb|left|Пример дерева]]
[[Файл:Euler graph.png|300px|thumb|right|Соответствующий эйлеров граф]]
Для представления [[Дерево, эквивалентные определения|дерева]] в виде [[Эйлеровость графов|эйлерового графа]] заменим каждое ребро <tex>\{u, v\} \</tex> дерева на два ребра <tex>(u, v)</tex> и <tex>(v, u)</tex>.
Получившийся [[Основные определения теории графов|ориентированный граф]] будет эйлеровым согласно [[Эйлеровость графов|критерию]].
<br>
<br>
<br>
<br>
<br>
<br>
<br>
<br>
Представим дерево в виде последовательности вершин, посещенных в порядке эйлерова обхода, начиная с вершины <tex>a</tex>.
[[Файл:Tour1.png|thumb|320px|center]]
==Операции c эйлеровыми обходами==
===Добавление ребра===
Для добавления ребра <tex>(c, g)</tex>:
*Выберем любое вхождение вершины <tex>c</tex> в эйлеров обход дерева <tex>T1</tex>.
*Разрежем эйлеров обход <tex>T1</tex> на две части:
*: <tex>A1</tex> {{---}} часть обхода до выбранного вхождения вершины <tex>c</tex>, включая ее.
*: <tex>A2</tex> {{---}} часть обхода после выбранного вхождения вершины <tex>c</tex>, включая ее.
*Аналогично, выберем любое вхождение вершины <tex>g</tex> в эйлеров обход дерева <tex>T2</tex> и разрежем его на две части <tex>B1</tex> и <tex>B2</tex>.
*Соберем результирующий эйлеров обход в порядке <tex>A1, B2, B1</tex> (без первой повторяющейся вершины), <tex>A2</tex>.
Чтобы быстро находить место, где разрезать эйлеровы обходы деревьев <tex>T1</tex> и <tex>T2</tex>, будем хранить эйлеровы обходы в двоичных деревьях поиска.
Ключом вершины для построения дерева поиска будет время посещения этой вершины эйлеровым обходом.
Для каждой вершины дерева <tex>(T1, T2)</tex> будем хранить указатель на вершину в дереве поиска, которая соответствует вхождению вершины дерева в эйлеров обход.
Тогда за <tex>O(1)</tex> переходим от вершины дерева к вершине дерева поиска, по которой за <tex>O(\log n)</tex> можно будет разделить дерево поиска на две части.
[[Файл:Link22.png |thumb|400px|center|Рис.1a Исходный лес <br>Рис.1b Эйлеровы обходы деревьев<br> Рис.1с Двоичные деревья поиска для хранения эйлеровых обходов <br> Рис.1d Результирующий эйлеров обход]]
===Разрезание ребра===
Для удаления ребра <tex>(g, j)</tex>:
*Найдем в эйлеровом обходе дерева <tex>T</tex> две пары посещений концов удаляемого ребра <tex>g,j</tex> и <tex>j,g</tex>, которые соответствуют прохождениям по ребру <tex>(g, j)</tex> в дереве <tex>T</tex>.
*Разрежем эйлеров обход дерева по этим парам на три части: <tex>A1, A2, A3</tex>.
*Соединив <tex>A1</tex> и <tex>A3</tex> (без повторяющейся первой вершины), получим эйлеров обход первого дерева, а <tex>A2</tex> дает эйлеров обход второго дерева.
Чтобы быстро находить места в эйлеровом обходе, которые соответствуют прохождению удаляемого ребра в дереве, будем для каждого ребра в дереве хранить ссылку на те места эйлерова обхода, где последовательно посещаем концы удаляемого ребра.
Так, для ребра <tex>(g, j)</tex> храним ссылки на узлы дерева поиска, соответствующие парам посещений концов этого ребра.
[[Файл:Link23.png |thumb|400px|center|Рис.1a Исходное дерево <br>Рис.1b Эйлеров обход исходного дерева<br> Рис.1с Двоичное дерево поиска для хранения эйлерового обхода <br> Рис.1d Эйлеровы обходы получившихся деревьев]]
===Проверка на связность===
Для того, чтобы проверить, лежат ли две вершины в одном дереве, достаточно подняться от вхождения каждой вершины в эйлеров обход (ссылку на которое мы храним) до корня дерева поиска, хранящего этот эйлеров обход.
==Способы реализации структуры==
===Сбалансированное дерево поиска===
Будем хранить последовательность вершин эйлерова обхода в виде сбалансированного двоичного дерева поиска, например, в виде [[Красно-черное дерево|красно-черного дерева]]. При построении дерева ключом вершины будет время посещения этой вершины эйлеровым обходом.
Операции объединения и разделения красно-черных деревьев выполняется за <tex>O(\log n)</tex><ref>[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.109.4875&rep=rep1&type=pdf Ron Wein {{---}} Efficient Implementation of Red-Black Trees.]</ref>.
===Декартово дерево по неявному ключу===
Также, можем хранить последовательности вершин эйлерова обхода в [[Декартово_дерево_по_неявному_ключу|декартовом дереве по неявному ключу]]. Глубина декартового дерева, построенного на массиве из <tex>n</tex> вершин, будет поддерживаться равной <tex>O(\log n)</tex>.
Операции объединения и разделения также выполняются за <tex>O(\log n)</tex>.
==См. также==
* [[Link-Cut Tree]]
== Примечания ==
<references/>
==Источники информации==
* [https://en.wikipedia.org/wiki/Euler_tour_technique Wikipedia {{---}} Euler tour technique]
* [http://courses.csail.mit.edu/6.851/spring07/scribe/lec05.pdf Advanced Data Structures {{---}} Euler tour trees]
* [http://codeforces.com/blog/entry/18369?mobile=true&locale=en CodeForces {{---}} On Euler tour trees]
* [http://logic.pdmi.ras.ru/csclub/node/2819 Лекториум{{---}} Лекция Павла Маврина об эйлеровых обходах]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Обходы графов]]
[[Категория: Эйлеровы графы]]
