Деревья Эйлерова обхода

Материал из Викиконспекты
Версия от 23:00, 18 декабря 2016; 91.215.122.38 (обсуждение) (Реализация структуры)
Перейти к: навигация, поиск

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

Задача:
Для динамически изменяющегося дерева выполнить следующие запросы:
  • [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 эйлеровыми обходами

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

Изменение корня дерева (переподвешивание)

Дано дерево с корнем в вершине [math]a[/math]. Требуется переподвесить его к вершине [math]h[/math].

Tour14.png

Для переподвешивания (англ. rerooting) необходимо:

  • Разбить эйлеров обход на три части:
    [math]S1[/math] - вершины, посещенные эйлеровым обходом до захода в [math]h[/math].
    [math]H[/math] - вершины между первым и последним вхождением нового корня [math]h[/math].
    [math]S2 [/math] - вершины, посещенные эйлеровым обходом после выхода из [math]h[/math].
  • Удалить первую вершину в [math]S1 [/math].
  • Соединить в следующем порядке: [math]H[/math], [math]S2 [/math], [math]S1 [/math].
  • Добавить [math]\{h\}[/math] в конец последовательности.
Tour13.png

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

Proba.png

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

Link11.png

Для связывания деревьев [math]T1 [/math] и [math]T2[/math], где [math]c\in T1\ [/math], а [math]g\in T2\[/math] добавлением ребра [math]\{c, g\} \[/math] необходимо:

  • Переподвесить дерево [math]T1[/math] к вершине [math]c[/math], если корнем дерева была другая вершина.
  • Переподвесить дерево [math]T2[/math] к вершине [math]g[/math], если корнем дерева была другая вершина.
  • Соединить получившиеся эйлеровы обходы.
  • Добавить [math]\{c\}[/math] в конец последовательности.
Link2.png

В результате получим эйлеров обход дерева с корнем в вершине [math]c[/math]:

Link3.png

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

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

См. также

Примечания

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