Метод Эйлера тура (ЭТТ) , названный в честь Леонарда Эйлера , является способ , в теории графов для представления деревьев . Дерево рассматривается как ориентированный граф , содержащий по два направленных ребра для каждого ребра в дереве. Затем дерево может быть представлено как эйлеров контур ориентированного графа, известный как представление эйлерова тура (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 )
- Для каждого ребра ( 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 элементов):
- Классифицируя наступление и отступление края: список Do рейтинга на ЕТР и сохранить результат в виде двумерного массива A . Тогда ( u , v ) является передним ребром, если и только если A ( u , v ) < A ( v , u ), и отступающим ребром в противном случае.
- Определите уровень каждого узла: произведите суммирование префиксов на ETR, где каждое переднее ребро считается как 1, а каждое отступающее ребро считается как -1. Тогда значение на переднем крае ( u , v ) - это уровень v .
- Количество узлов в поддереве с корнем v : определите переднюю кромку ( u , v ) и отступающую кромку ( u , v ) параллельно, а затем подсчитайте количество продвинутых ребер между ( u , v ) и ( u , v) ) с использованием суммы префикса.
- Индекс поиска в глубину узла v : подсчитать количество продвинутых ребер до ( u , v ) включительно .
- Определите наименьшего общего предка двух узлов.
Деревья Эйлера тура [ править ]
Хенцингер и Кинг [2] предлагают представить данное дерево, сохраняя его эйлеров тур в сбалансированном двоичном дереве поиска , с ключом по индексу в обходе. Так, например, несбалансированное дерево в приведенном выше примере, имеющее 7 узлов, будет представлено сбалансированным двоичным деревом с 14 узлами, по одному на каждый раз, когда каждый узел появляется в туре.
Мы можем представить лес (ациклический граф), используя набор деревьев ET - одно дерево ET на одно дерево леса. Это представление позволяет нам быстро ответить на вопрос «что является корнем узла v?» просто перейдя к первому узлу ET-дерева (поскольку узлы в ET-дереве имеют ключи в соответствии с их положением в обходе Эйлера, а корень является первым и последним узлом в обходе). Когда представленный лес обновляется (например, путем соединения двух деревьев с одним деревом или путем разделения дерева на два дерева), соответствующая структура эйлер-тура может быть обновлена за время O (log (n)).
Связать / вырезать деревья имеют аналогичные гарантии производительности. В то время как деревья LC хороши для поддержания агрегатов на путях дерева (что делает их хорошей структурой данных выбора в алгоритмах сетевого потока), деревья ET лучше хранят агрегированную информацию о поддеревьях. [3]
Ссылки [ править ]
- ^ Tarjan, RE; Вишкин, У. (1984). Нахождение двусвязных компонентов и вычисление древовидных функций за логарифмическое параллельное время . Труды FOCS. С. 12–20. CiteSeerX 10.1.1.419.3088 . DOI : 10.1109 / SFCS.1984q5896 .
- ^ Хенцингер, MR; Кинг, В. (1995). «Рандомизированные алгоритмы динамического графа с полилогарифмическим временем на операцию». Материалы двадцать седьмого ежегодного симпозиума ACM по теории вычислений - STOC '95 . п. 519. DOI : 10,1145 / 225058,225269 . ISBN 0897917189.
- ^ Деревья тура Эйлера - в конспектах лекций в расширенных структурах данных. Профессор Эрик Демейн; Писец: Кэтрин Лай.