Изменения

==ВведениеЗадача о динамической связности=={{Задача|definition = Для решения задачи о динамической связности (англ.''dynamic connectivity problem'') требуется выполнение следующих операцийдинамически изменяющегося дерева выполнить следующие запросы:* '''<tex>\mathrm{link(u, w)}</tex>''' {{---}} добавить ребро <tex>(u, w) </tex> (при условии, что вершины <tex>u </tex> и <tex>w </tex> принадлежат разным деревьям),* '''<tex>\mathrm{cut(u, w)}</tex>''' {{---}} разрезать ребро <tex>(u, w) </tex> (при условии, что ребро <tex>(u, w) </tex> принадлежит дереву),* '''<tex>\mathrm{isConnected(u, w)}</tex>''' {{---}} определить принадлежат ли вершины <tex>u </tex> и <tex>w </tex> одной компоненте связности.}}

'''Дерево Для решения поставленной задачи будем представлять дерево в виде его [[Эйлеровость графов|эйлерова обхода''' графа]], а затем будем работать с [[Эйлеровость графов|эйлеровым обходом]] (англ.''Euler tour tree'') {{---}} способ представления динамического дерева, позволяющий этого графа. Это позволит выполнять указанные операции запросы за <tex>O(\log n)</tex>.

==Свойство эйлерова обхода== Представим дерево в виде последовательности вершин, посещеннных посещенных в порядке эйлерова обхода , начиная с корнем в вершине вершины <tex>a</tex>.

==Операции c эйлеровыми обходами=Изменение корня дерева (переподвешивание)===Дано дерево с корнем в вершине <tex>a</tex>. Требуется переподвесить его к вершине <tex>h</tex>. [[Файл:Tour13.png |thumb|320px|center]] Для переподвешивания (англ. ''rerooting'') необходимо:*Разбить эйлеров обход на три части <tex>S1 </tex>, <tex>H</tex>, и <tex>S2 </tex>, где <tex>H</tex> состоит из вершин между первым и последним вхождением нового корня <tex>h</tex>.*Удалить первую вершину в <tex>S1 </tex>.*Соединить в следующем порядке: <tex>H</tex>, <tex>S2 </tex>, <tex>S1 </tex>.*Добавить <tex>\{h\}</tex> в конец последовательности. В результате получим: [[Файл:Proba.png |center]]

[[ФайлДля добавления ребра <tex>(c, g)</tex>:Link11*Выберем любое вхождение вершины <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>.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>T1</tex> к вершине <tex>c</tex>которая соответствует вхождению вершины дерева в эйлеров обход.*Переподвесить дерево Тогда за <tex>T2O(1)</tex> переходим от вершины дерева к вершине дерева поиска, по которой за <tex>g</tex>.*Соединить получившиеся эйлеровы обходы.*Добавить <tex>\{cO(\}log n)</tex> в конец последовательностиможно будет разделить дерево поиска на две части.

[[Файл:Link2Link22.png|thumb|400px |center]] В результате получим: [[Файл:Link3|Рис.1a Исходный лес <br>Рис.1b Эйлеровы обходы деревьев<br> Рис.png|center1с Двоичные деревья поиска для хранения эйлеровых обходов <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> (1без повторяющейся первой вершины), получим эйлеров обход первого дерева, а <tex>A2</tex> дает эйлеров обход второго дерева.

Для каждой вершины Чтобы быстро находить места в эйлеровом обходе, которые соответствуют прохождению удаляемого ребра в дереве, будем для каждого ребра в дереве хранить указатели ссылку на первое и последнее вхождение вершины в последовательностьте места эйлерова обхода, где последовательно посещаем концы удаляемого ребра. Тогда возможно определять первое и последнее вхождение вершины за ОТак, для ребра <tex>(1g, j)</tex> храним ссылки на узлы дерева поиска, соответствующие парам посещений концов этого ребра.

Однако,используя двусвязные списки определение принадлежности вершин одной компоненте связности занимает О(n) в худшем случае[[Файл:Link23.png |thumb|400px|center|Рис.1a Исходное дерево <br>Рис.1b Эйлеров обход исходного дерева<br> Рис.1с Двоичное дерево поиска для хранения эйлерового обхода <br> Рис.1d Эйлеровы обходы получившихся деревьев]]

===Balanced TreesПроверка на связность===Для того, чтобы проверить, лежат ли две вершины в одном дереве, достаточно подняться от вхождения каждой вершины в эйлеров обход (ссылку на которое мы храним) до корня дерева поиска, хранящего этот эйлеров обход.

Будем хранить последовательность вершин эйлерова обхода в виде сбалансированного двоичного дерева поиска, например, в виде [[Файл:Balanced tree.png |centerКрасно-черное дерево|Пример красно-черного дерева]]. При построении дерева ключом вершины будет время посещения этой вершины эйлеровым обходом.

Observation Операции объединения и разделения красно-черных деревьев выполняется за <tex>O(\log n)</tex><ref>[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1: Can still store pointers to the first and last occurrence .1.109.4875&rep=rep1&type=pdf Ron Wein {{---}} Efficient Implementation of each tree nodeRed-Black Trees.]</ref>.

Observation 3: RedТакже, можем хранить последовательности вершин эйлерова обхода в [[Декартово_дерево_по_неявному_ключу|декартовом дереве по неявному ключу]]. Глубина декартового дерева, построенного на массиве из <tex>n</black trees can be split and joined in time tex> вершин, будет поддерживаться равной <tex>O(\log n) each</tex>.

[[Файл:Balanced tree1Операции объединения и разделения также выполняются за <tex>O(\log n)</tex>.png |center|Пример ]]

The data structure:<br>Represent each tree as an Euler tour.<br>Store those sequences as balanced binary trees.<br>Each node in the original forest stores a pointer to its first and last occurrence.<br>Each node in the balanced trees stores a pointer to its parent==См.<br>также==link, cut, and is* [[Link-connected queries take time only O(log n) each.Cut Tree]]

==Похожие [[Категория: Алгоритмы и структуры==данных]]Про link-cut trees[[Категория: Обходы графов]][[Категория: Эйлеровы графы]]