Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

В комбинаторной математике и теоретическая информатике , разложение тяжелого пути (также называемый тяжелый свет разложение ) представляет собой метод разложения корневого дерева в набор путей . В разложении тяжелого пути каждый нелистовой узел выбирает одно «тяжелое ребро», ребро дочернего элемента, имеющего наибольшее количество потомков (разрывая связи произвольно). Выбранные ребра образуют пути разложения.

Разложение на пути [ править ]

Если ребра дерева T разделены на набор тяжелых ребер и легких ребер, с одним тяжелым ребром от каждого нелистового узла к одному из его дочерних элементов, то подграф, образованный тяжелыми ребрами, состоит из набора путей, с каждой нелистовой вершиной, принадлежащей ровно одному пути, содержащему его тяжелое ребро. Конечные узлы дерева, которые не являются конечной точкой тяжелого ребра, можно рассматривать как образующие пути нулевой длины. Таким образом, каждая вершина принадлежит ровно одному из путей. У каждого пути есть верхняя вершина, самая верхняя вершина.

В качестве альтернативы, пути с толстыми краями могут быть расширены за счет включения одного светлого края, от начала пути до его родителя. [1] В этом варианте разложения некоторые вершины принадлежат нескольким путям, но каждое ребро T принадлежит ровно одному пути.

Дерево путей [ править ]

Сами пути разложения могут быть организованы в дерево, называемое «дерево путей», «дерево тяжелых путей» или «сжатое дерево». Каждый узел дерева путей соответствует пути декомпозиции тяжелого пути. Если p - путь разложения тяжелого пути, то родительский элемент p в дереве путей - это путь, содержащий родительский элемент заголовка p . Корень дерева путей - это путь, содержащий корень исходного дерева. В качестве альтернативы, дерево путей может быть сформировано из исходного дерева путем стягивания всех тяжелых ребер.

«Легкое» ребро данного дерева - это ребро, которое не было выбрано при декомпозиции тяжелого пути. Если светлое ребро соединяет два узла дерева x и y , причем x является родителем y , то x должен иметь как минимум вдвое больше потомков, чем y . Следовательно, на любом пути от корня к листу дерева с n узлами может быть не более log 2  n светлых ребер. Эквивалентно, дерево путей имеет высоту не более log 2  n .

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

Декомпозиция тяжелых путей была введена Sleator & Tarjan (1983) как часть амортизированного анализа их структуры дерева связей / отсечений [2] и Harel & Tarjan (1984) как часть их структуры данных для низших общих предков , [3 ] Структура данных дерева связывания / вырезания использует разделение динамического дерева на пути, которое не обязательно является декомпозицией тяжелых путей; его анализ использует потенциальную функциюизмерение его расстояния от разложения тяжелого пути, а небольшая высота дерева путей подразумевает, что каждая операция структуры данных выполняет только небольшое количество шагов, которые не могут быть оплачены улучшением этой функции. [2] В структуре данных самого низкого общего предка декомпозиция используется для встраивания входного дерева в полное двоичное дерево логарифмической глубины, позволяя решать каждый запрос с помощью побитовых операций с постоянным временем . [3]

Последующие применения декомпозиции тяжелого пути включали решение проблемы предков уровня , [4] вычисление расстояния редактирования между деревьями, [5] [6] рисование графа и жадное встраивание , [7] [8] [9] нахождение пути около всех узлы данного графа, [10] диагностика неисправностей в волоконно-оптическом коммуникационных сетях, [1] и декодирование грамматики на основе кодов , [11] среди других.

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

  1. ^ а б Харви, Николас JA; Пэтрашку, Михай ; Вэнь, Юнган; Еханин, Сергей; Чан, Винсент WS (2007), «Non-адаптивная диагностика неисправностей для всех-оптических сетей с помощью комбинаторной тестировании группы на графах», двадцать шестого IEEE Международной конференции по компьютерной связи (INFOCOM 2007) , стр 697-705,. Дои : 10,1109 / INFCOM .2007,87
  2. ^ a b Sleator, Дэниел Д .; Тарьян, Роберт Эндре (1983), "Структура данных для динамических деревьев", журнал компьютерных и системных наук , 26 (3): 362-391, DOI : 10,1016 / 0022-0000 (83) 90006-5 , MR 0710253 
  3. ^ a b Харель, Дов; Тарьян, Роберт Е. (1984), "Быстрые алгоритмы поиска ближайших общих предков", SIAM журнал по вычислениям , 13 (2): 338-355, DOI : 10,1137 / 0213024
  4. ^ Дитц, Пол Ф. (1991), «Поиск предков уровней в динамических деревьях», Алгоритмы и структуры данных (Оттава, Онтарио, 1991) , Лекционные заметки по компьютерным наукам, 519 , Берлин: Springer, стр. 32-40, DOI : 10.1007 / BFb0028247 , МР 1146687 
  5. ^ Кляйн, Филип Н. (1998), «Вычисление расстояния редактирования между упорядоченными деревьями без корня», Алгоритмы - ESA '98 (Венеция) , Лекционные заметки по компьютерным наукам, 1461 , Берлин: Springer, стр. 91–102, doi : 10.1007 / 3-540-68530-8_8 , Руководство по ремонту 1683332 
  6. ^ Demaine, Эрик Д .; Мозес, Шей; Россман, Бенджамин; Вейманн, Орен (2010), «Оптимальный алгоритм декомпозиции для расстояния редактирования дерева», Транзакции ACM по алгоритмам , 6 (1): A2, doi : 10.1007 / 978-3-540-73420-8_15 , MR 2654906 
  7. ^ Buchsbaum, Адам L .; Вестбрук, Джеффри Р. (2000), «Поддержание иерархических представлений графов», Материалы одиннадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (Сан-Франциско, Калифорния, 2000) , Нью-Йорк: ACM, стр. 566–575, MR 1755515 
  8. ^ Эппштейн, Дэвид ; Гудрич, Майкл Т. (2011), "Succinct жадные геометрической маршрутизации с использованием гиперболической геометрии", IEEE Transactions на компьютерах , 60 (11): 1571-1580, DOI : 10,1109 / TC.2010.257 , МР 2830035 
  9. ^ Дункан, Кристиан А .; Эпштейн, Дэвид ; Гудрич, Майкл Т .; Кобуров, Стивен Г .; Нелленбург, Мартин (2013), «Рисование деревьев с идеальным угловым разрешением и полиномиальной площадью», Дискретная и вычислительная геометрия , 49 (2): 157–182, arXiv : 1009.0581 , doi : 10.1007 / s00454-012-9472-y , MR 3017904 
  10. ^ Альструп, Стивен; Лауридсен, Питер В; Зоммерлунд, Пер; Thorup, Mikkel (1997), «Поиск ядер ограниченной длины», Алгоритмы и структуры данных , Лекционные заметки в томе компьютерных наук, 1272 , Springer, стр. 45–54, DOI : 10.1007 / 3-540-63307-3_47
  11. ^ Билле, Филипп; Landau, Gad M .; Раман, Раджив; Садакане, Кунихико; Сатти, Шриниваса Рао; Вейманн, Орен (2011), «Произвольный доступ к строкам, сжатым грамматикой», Труды двадцать второго ежегодного симпозиума ACM-SIAM по дискретным алгоритмам , Филадельфия, Пенсильвания: SIAM, стр. 373–389, MR 2857133