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

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

Строительство [ править ]

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

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

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

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

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

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

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

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

Приложения [ править ]

Все следующие проблемы могут быть решены за O (Prefix sum ( n )) (время, необходимое для решения задачи суммы префиксов параллельно для списка из n элементов):

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

Деревья Эйлера тура [ править ]

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

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

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

Ссылки [ править ]

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