29
правок
Изменения
Нет описания правки
Рассмотрим полное ветвящееся дерево <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)</math>, алгоритм находит ребро с наибольшим весом на пути между двумя листьями следующим образом. Для всех листьев в дереве находится их наименьший общий предок, например, с помощью [[Алгоритм Тарьяна поиска LCA за O(1) в оффлайн|алгоритма Тарьяна]] со сложностью <math>O(|V| + |E|)</math>. Пусть для некоторых двух листьев <math>l_i, l_j</math> их наименьший общий предок <math>LCA(l_i, l_j) = v</math>. Тогда ребром с наибольшим весом на пути из <math>l_i</math> в <math>l_j</math> будет ребро <math>e = \arg\max\{w(A(v, l_i)), w(A(v, l_j))\}</math>.
Комлос показал, что <math>\sum\limits_{v\in T} \log |A(v)| = O\left(|V_TV|\log\left(\frac{|E_TE|+|V_TV|}{|V_TV|}\right)\right)</math>, что дает верхнюю границу для количества операций сравнений, используемых алгоритмом.
==== Эффективная реализация при помощи битового сжатия ====
В работе Валери Кинг был предложен [[Алгоритм Кинг|метод сведения общего случая остовного дерева к полному ветвящемуся дереву]], а также предложена эффективная реализация алгоритма Комлоса с использованием битового сжатия<ref name="kingalg">King, V. A simpler minimum spanning tree verification algorithm. Algorithmica 18, 263–270 (1997). https://doi.org/10.1007/BF02526037</ref>. Описанные в работе структуры данных и битовые операции, которые возможно предвычислить и сохранить в таблице, обращение к которой занимает константное количество операций, позволяют выполнить алгоритм Комлоса за линейное время.
