Техника тура Эйлера - Euler tour technique

Эйлеров тур по дереву, края которого помечены, чтобы показать порядок, в котором они пересекаются при обходе.

В Техника Эйлера-тура (ЭТТ), названный в честь Леонард Эйлер, это метод в теория графов для представления деревья. Дерево рассматривается как ориентированный граф который содержит два направленных ребра для каждого ребра в дереве. Тогда дерево можно представить как Контур Эйлера ориентированного графа, известного как Представительство Эйлера тура (ETR) дерева. ETT позволяет эффективно, параллельное вычисление решений общих проблем в алгоритмическая теория графов. Он был введен Тарьяном и Вишкиным в 1984 году.[1]

Строительство

Для неориентированного дерева, представленного в виде набора ребер, представление тура Эйлера (ETR) может быть построено параллельно следующим образом:

  • Строим симметричный список ориентированных ребер:
    • Для каждого неориентированного ребра {ты,v} в дереве вставьте (ты,v) и (v,ты) в списке краев.
  • Сортировать список краев лексикографически. (Здесь мы предполагаем, что узлы дерева упорядочены, и что корень является первым элементом в этом порядке.)
  • Создайте списки смежности для каждого узла (называемого следующий) и карту от узлов к первым записям списков смежности (называемых первый):
    • Для каждого ребра (ты,v) в списке параллельно выполните:
      • Если предыдущее ребро (Икс,у) имеет Икс ≠ ты, т.е. начинается с другого узла, устанавливается первым (ты) = (ты,v)
      • Иначе, если Икс = ты, т.е. начинается с того же узла, установить следующий (Икс,у) = (ты,v)

Создайте список ребер (называемый succ) в порядке обхода Эйлера, задав указатели succ (ты,v) для всех ребер (ты,v) параллельно по следующему правилу:

Результирующий список succ будет круглым.

Общая конструкция требует работы W(п) = O (сортировать (п)) (время, необходимое для сортировки п элементы параллельно), если в дереве есть п узлов, так как в деревьях количество ребер на единицу меньше количества узлов.

Корни, края продвижения и отступления

Если у дерева есть корень, мы можем разбить круговой список succ в этом корне. В этом случае мы можем говорить о продвигать и спасаться бегством ребра: задана пара узлов ты,v, первое вхождение либо (ты,v) или же (v,ты) в ETR называется передний край, а второе вхождение называется край отступления. Это напоминает интуицию, что при первом прохождении такого ребра расстояние до корня увеличивается, а во второй раз расстояние уменьшается.

Перенастроить дерево можно за постоянное время O (1), разделив круговой список succ в новом корне.

Приложения

Все следующие проблемы можно решить за O (Префиксная сумма (п)) (время, необходимое для решения сумма префикса проблема параллельно для списка п Предметы):

  1. Классификация ребер наступления и отступления: составьте список ранжирования по ETR и сохраните результат в двумерном массиве А. Потом (ты,v) является передовым фронтом тогда и только тогда, когда А(ты,v) < А(v,ты), и отступление в противном случае.
  2. Определите уровень каждого узла: произведите суммирование префикса на ETR, где каждое продвинутое ребро считается как 1, а каждое отступающее ребро считается как -1. Тогда значение на переднем крае (ты,v) - уровень v.
  3. Количество узлов в поддереве с корнем v: определить передний край (ты,v), а край отхода (ты,v) параллельно, а затем подсчитайте количество передних кромок между (ты,v) и (ты,v) с использованием суммы префикса.
  4. В поиск в глубину индекс узла v: подсчитать количество продвинутых ребер до (ты,v).
  5. Определите наименьшего общего предка двух узлов.

Деревья Эйлера-тура

Хенцингер и Кинг[2] предложить представить данное дерево, сохраняя его тур Эйлера в сбалансированное двоичное дерево поиска, введенный индексом в туре. Так, например, несбалансированное дерево в приведенном выше примере, имеющее 7 узлов, будет представлено сбалансированным двоичным деревом с 14 узлами, по одному на каждый раз, когда каждый узел появляется в туре.

Мы можем представить лес (ациклический граф), используя набор деревьев ET - одно дерево ET на одно дерево леса. Это представление позволяет нам быстро ответить на вопрос «что является корнем узла v?» просто перейдя к первому узлу ET-дерева (поскольку узлы в ET-дереве имеют ключи по их положению в обходе Эйлера, а корень является первым и последним узлом в обходе). Когда представленный лес обновляется (например, путем соединения двух деревьев с одним деревом или путем разделения дерева на два дерева), соответствующая структура тура Эйлера может быть обновлена ​​за время O (log (n)).

Связывание / рубка деревьев имеют аналогичные гарантии производительности. В то время как деревья LC хороши для поддержки агрегатов на путях дерева (что делает их хорошей структурой данных выбора в алгоритмах сетевого потока), деревья ET лучше хранят агрегированную информацию о поддеревьях.[3]

Рекомендации

  1. ^ Tarjan, R.E .; Вишкин, У. (1984). Поиск двусвязных компонентов и вычисление древовидных функций за логарифмическое параллельное время. Труды FOCS. С. 12–20. CiteSeerX  10.1.1.419.3088. Дои:10.1109 / SFCS.1984q5896.
  2. ^ Henzinger, M. R .; Кинг, В. (1995). «Рандомизированные алгоритмы динамического графа с полилогарифмическим временем на операцию». Материалы двадцать седьмого ежегодного симпозиума ACM по теории вычислений - STOC '95. п. 519. Дои:10.1145/225058.225269. ISBN  0897917189.
  3. ^ Деревья Эйлера-тура - в конспектах лекций в расширенных структурах данных. Профессор Эрик Демейн; Писец: Кэтрин Лай.