Изменения

Перейти к: навигация, поиск

Алгоритм Комлоса

2251 байт добавлено, 16:08, 25 января 2022
Нет описания правки
'''Алгоритм Комло́са''' {{---}} алгоритм, разработанный Яношем Комлосом (''венг. Komlós János''). Алгоритм предназначен для поиска ребра с наибольшим весом на путях между каждой парой вершин в подвешенных деревьях. Поиск таких рёбер используется при верификации [[Лемма о безопасном ребре#Необходимые определения | минимального остовного дерева]] путем проверки [[Критерий Тарьяна минимальности остовного дерева|критерия Тарьяна]].
 
Пусть существует некоторый взвешенный неориентированный граф <math>G</math> и его остовное дерево <math>T</math>. Допустим, что для каждого ребра <math>\{u, v\}</math> графа <math>G</math>, не входящего в дерево <math>T</math>, существует способ найти ребро с наибольшим весом в пути между вершинами <math>u, v</math> в дереве <math>T</math>. Тогда для проверки критерия Тарьяна достаточно сравнить веса таких рёбер с весами рёбер <math>\{u, v\}</math>.
== Описание алгоритма ==
=== Случай полного ветвящегося дерева ===
==== Общее описание подхода ====
Рассмотрим полное ветвящееся дерево <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>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>. Описанные в работе структуры данных и битовые операции, которые возможно предвычислить и сохранить в таблице, обращение к которой занимает константное количество операций, позволяют выполнить алгоритм Комлоса за линейное время.
В завершении алгоритма, требуется сравнить веса рёбер графа, которые не входят в остовное дерево, с найденными в остовном дереве рёбрами наибольшего веса, что потребует дополнительных <math>O(m)</math> операций сравнения, где <math>m</math> {{---}} количество рёбер в исходном графе.
 
== См. также ==
* [[Критерий Тарьяна минимальности остовного дерева]]
* [[Алгоритм Кинг]]
* [[Алгоритм Тарьяна поиска LCA за O(1) в оффлайн]]
== Источники информации ==
* Komlós, J. Linear verification for spanning trees. Combinatorica 5, 57–65 (1985). https://doi.org/10.1007/BF02579443
== Примечания ==
<references/>
 
[[Категория:Алгоритмы на графах]]
[[Категория:Построение остовных деревьев]]
29
правок

Навигация