Изменения

Рассмотрим полное ветвящееся дерево <math>T= (V, E)</math>, т.е. такое дерево, у вершин которого либо 0, либо 2 и более потомков, и все листья находятся на одном уровне. Для такого дерева Комлосом был показан вариант алгоритма, который находит ребро с максимальным весом на пути для каждой пары листьев, используя <math>O\left(n\log\left(\frac{m+n}{n}\right)\right)</math> операций сравнения. Алгоритм разбивает путь между листьями на две части, начинающихся в листе и заканчивающихся в наименьшем общем предке этих листьев, и находит ребро с наибольшим весом в каждой части. После чего, одно из двух рёбер с большим весом выбирается ребром с наибольшим весом на пути из одной вершины в другую. Алгоритм вычисляет вес для каждой части пути следующим образом. Пусть <math>A(v, l)</math> {{---}} ребро максимального веса на пути из корня в некоторый лист <math>l</math>, проходящий через вершину <math>v</math>, ограниченном на отрезке <math>[v, l]</math> (т.е. удалены все вершины от корня до предка v). Обозначим <math>A(v) = \{A(v, l) | l \text{ содержится в поддереве с корнем } v\}</math> и <math>w(e)</math> - вес ребра <math>e</math>.Предположим, что <math>s</math> {{---}} вершина-потомок <math>v</math>, и известно множество <math>A(s) = \{A(s, l_1), A(s, l_2),\dots\}</math>. Рассмотрим случай одного листа <math>l_i</math>. Очевидно, что все пути из корня в <math>l_i</math>, проходящие через <math>s</math>, также проходят через <math>v</math>. Так как ребро <math>\{v, s\}</math> связывает <math>v</math> и <math>s</math>, получим, что <math>A(v, l_i) = \arg\max\{w(A(s, l_i)), w(\{v, s\})\}</math>, где <math>w(e)</math> - вес ребра <math>e</math>. Следовательно, для того, чтобы найти <math>A(v)</math>, достаточно сравнить веса рёбер из <math>A(s)</math> с весом ребра <math>\{v, s\}</math>. Данное сравнение можно эффективно выполнить с помощью двоичного поиска. Итоговое множество <math>A(v)</math> получается путем объединением множеств рёбер, полученных для каждого потомка. Таким образом, алгоритм, начиная с корня дерева, спускается до листьев графа и конструирует множества <math>A(v)</math> для каждой вершины.

Алгоритм вычисляет вес для каждой части пути следующим образом. Пусть После нахождения множеств <math>A(v, l)</math> {{---}} , алгоритм находит ребро максимального веса с наибольшим весом на пути из корня между двумя листьями следующим образом. Для всех листьев в некоторый лист <math>l</math>дереве находится их наименьший общий предок, проходящий через вершину <math>v</math>например, ограниченном на отрезке <math>с помощью [[v, l]</math> Алгоритм Тарьяна поиска LCA за O(т.е. удалены все вершины от корня до предка v1). Обозначим в оффлайн|алгоритма Тарьяна]] со сложностью <math>AO(v) = \{A(v, l|V| + |E|) | l \text{ содержится в поддереве с корнем } v\}</math>.Предположим, что Пусть для некоторых двух листьев <math>sl_i, l_j</math> {{---}} вершина-потомок их наименьший общий предок <math>v</math>LCA(l_i, и известно множество <math>A(sl_j) = \{A(s, l_1), A(s, l_2),\dots\}v</math>. Рассмотрим случай одного листа <math>l_i</math>. Очевидно, что все Тогда ребром с наибольшим весом на пути из корня в <math>l_i</math>, проходящие через в <math>sl_j</math>, также проходят через <math>v</math>. Так как будет ребро <math>\{v, s\}</math> связывает <math>v</math> и <math>s</math>, получим, что <math>A(v, l_i) e = \arg\max\{w(A(sv, l_i)), w(\{v, s\})\}</math>, где <math>w(e)</math> - вес ребра <math>e</math>. Следовательно, для того, чтобы найти <math>A(v, l_j)</math>, достаточно сравнить веса рёбер из <math>A(s)</math> с весом ребра <math>\{v, s\}</math>. Данное сравнение можно эффективно выполнить с помощью двоичного поиска. Итоговое множество <math>A(v)</math> получается путем объединением множеств рёбер, полученных для каждого потомка.