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

Материал из Викиконспекты
Версия от 01:17, 31 декабря 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 эйлеровыми обходами

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

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

Link11.png

Для добавления ребра (c, g):

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

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

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

Cut1.png

Для удаления ребра [math]\{g, j\} \[/math]:

  • Найдем в эйлеровом обходе дерева T две пары посещений концов удаляемого ребра gj и jg, которые соответствуют прохождениям по ребру (g, j) в T.
  • Разрежем эйлеров обход дерева по этим парам на 3 части: A1, A2, A3
  • Соберем результирующий обход в порядке A1, A3, A2

Чтобы быстро находить места в эйлеровом обходе, которые соответствуют прохождению удаляемого ребра в дереве, будем для каждого ребра в дереве хранить ссылку на те места эйлерова обхода, где последовательно посещаем концы удаляемого ребра. Так,

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

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

Balanced tree.png

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

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

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

Balanced tree1.png

См. также

Примечания

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