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

Эта статья находится в разработке!

Алгоритм Комло́са — алгоритм, разработанный Яношем Комлосом (венг. Komlós János). Алгоритм предназначен для поиска ребра с наибольшим весом на путях между каждой парой вершин в подвешенных деревьях. Поиск таких рёбер используется при верификации минимального остовного дерева путем проверки критерия Тарьяна.

Пусть существует некоторый взвешенный неориентированный граф $G$ и его остовное дерево $T$. Допустим, что для каждого ребра $\{u, v\}$ графа $G$, не входящего в дерево $T$, существует способ найти ребро с наибольшим весом в пути между вершинами $u, v$ в дереве $T$. Тогда для проверки критерия Тарьяна достаточно сравнить веса таких рёбер с весами рёбер $\{u, v\}$.

Описание алгоритма

Случай полного ветвящегося дерева

Общее описание подхода

Рассмотрим полное ветвящееся дерево $T = (V, E)$, т.е. такое дерево, у вершин которого либо 0, либо 2 и более потомков, и все листья находятся на одном уровне. Для такого дерева Комлосом был показан вариант алгоритма, который находит ребро с максимальным весом на пути для каждой пары листьев, используя $O\left(n\log\left(\frac{m+n}{n}\right)\right)$ операций сравнения. Алгоритм разбивает путь между листьями на две части, начинающихся в листе и заканчивающихся в наименьшем общем предке этих листьев, и находит ребро с наибольшим весом в каждой части. После чего, одно из двух рёбер с большим весом выбирается ребром с наибольшим весом на пути из одной вершины в другую.

Алгоритм вычисляет вес для каждой части пути следующим образом. Пусть $A(v, l)$ — ребро максимального веса на пути из корня в некоторый лист $l$, проходящий через вершину $v$, ограниченном на отрезке $[v, l]$ (т.е. удалены все вершины от корня до предка v). Обозначим $A(v) = \{A(v, l) | l \text{ содержится в поддереве с корнем } v\}$. Предположим, что $s$ — вершина-потомок $v$, и известно множество $A(s) = \{A(s, l_1), A(s, l_2),\dots\}$. Рассмотрим случай одного листа $l_i$. Очевидно, что все пути из корня в $l_i$, проходящие через $s$, также проходят через $v$. Так как ребро $\{v, s\}$ связывает $v$ и $s$, получим, что $A(v, l_i) = \arg\max\{w(A(s, l_i)), w(\{v, s\})\}$, где $w(e)$ - вес ребра $e$. Следовательно, для того, чтобы найти $A(v)$, достаточно сравнить веса рёбер из $A(s)$ с весом ребра $\{v, s\}$. Данное сравнение можно эффективно выполнить с помощью двоичного поиска. Итоговое множество $A(v)$ получается путем объединением множеств рёбер, полученных для каждого потомка. Таким образом, алгоритм, начиная с корня дерева, спускается до листьев графа и конструирует множества $A(v)$ для каждой вершины.

После нахождения множеств $A(v)$, алгоритм находит ребро с наибольшим весом на пути между двумя листьями следующим образом. Для всех листьев в дереве находится их наименьший общий предок, например, с помощью алгоритма Тарьяна со сложностью $O(|V| + |E|)$. Пусть для некоторых двух листьев $l_i, l_j$ их наименьший общий предок $LCA(l_i, l_j) = v$. Тогда ребром с наибольшим весом на пути из $l_i$ в $l_j$ будет ребро $e = \arg\max\{w(A(v, l_i)), w(A(v, l_j))\}$.

Комлос показал, что $\sum\limits_{v\in T} \log |A(v)| = O\left(|V|\log\left(\frac{|E|+|V|}{|V|}\right)\right)$, что дает верхнюю границу для количества операций сравнений, используемых алгоритмом.

Эффективная реализация при помощи битового сжатия

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

Обозначим за $T=(V, E)$ полное ветвящееся дерево, полученное с помощью алгоритма Кинг. Вершины в дереве нумеруются битовыми словами следующим образом:

1. Каждый лист помечается порядковым номером 0, 1, 2... в двоичном представлении в порядке встречи листов при обходе в глубину.
2. Каждый не-лист помечается номером своего потомка, содержащим наибольшее количество ведущих нулей.

Рёбра в дереве получают тег, который формируется следующим образом. Рассмотрим ребро $e = \{u, v\}$, где $v$ находится дальше от корня. Пусть $d(v)$ обозначает расстояние от вершины $v$ до корня, а $i(v)$ — номер младшей единицы в номере вершины $v$. Тогда тег ребра $e$ — строка размера $\lceil\lg\lg |V|\rceil$, записанная как последовательность $\lt d(v), i(v)\gt$. В оригинальной работе было показано, что имея тег ребра и номер вершины, можно обнаружить ребро в графе за константное время.

Для каждой вершины $v$ создается вектор длины $\lceil\lg|V|\rceil$, обозначаемый как $LCA(v)$, чей бит с номером i равен 1 тогда, когда существует путь из листа в поддереве с корнем $v$ в лист в другом поддереве, наивысшая по уровню вершина которого (иначе говоря, наименьший общий предок двух листьев) находится на расстоянии $i$ от $v$.

Далее, вершины делятся на два класса. Если $|A(v)|\gt \frac{\lceil\lg|V|\rceil}{\lceil\lg\lg |V|\rceil}$, то вершина $v$ считается большой; в противном случае вершина считается малой. Для больших вершин создаются списки $bigList$, для малых — $smallList$. $BigList$ содержит теги рёбер из $A(v)$ в порядке неубывания длин путей из корня в листья, соответствующих рёбрам. Для хранения такого списка требуется $\frac{|A(v)|\lceil\lg\lg |V|\rceil}{\lceil\lg|V|\rceil}=O(\log\log |V|)$ памяти.

Для малой вершины $v$ обозначим за $a$ ближайшего большого предка. Список $smallList$ содержит либо теги рёбер из $A(v)$, либо, если ребро $e$ из $A(v)$ содержится в интервале от корня до $a$, указатель на $bigList$ вершины $a$, содержащий тег для $e$. Для каждой малой вершины запоминается номер первого элемента в $smallList$, являющимся тегом. Элементы списка, идущие после первого тега, тоже являются тегами. Для хранения $smallList$ требуется одно битовое слово.

Анализ сложности

Было показано, что в реализации с битовым сжатием операции для малых вершин выполняются за константное время. Если вершина большая, то стоимость предвычислений для неё составляет $|A(v)|\frac{\lceil\lg\lg |V|\rceil}{\lceil\lg|V|\rceil} = \Omega\left(\log |A(v)|\right)$ операций. Следовательно, общая сложность предвычислений составляет $O(\log |A(v)|)$ операций. Дополнительно алгоритм тратит $O(|V|+|E|)$ операций для построения списков $LCA(v)$, $O(|V|)$ операций для обработки таблиц с предвычисленными значениями и $O(|E|)$ операций сравнения для нахождения ребра с максимальным весом из двух половин.

В завершении алгоритма, требуется сравнить веса рёбер графа, которые не входят в остовное дерево, с найденными в остовном дереве рёбрами наибольшего веса, что потребует дополнительных $O(m)$ операций сравнения, где $m$ — количество рёбер в исходном графе.

См. также

• Критерий Тарьяна минимальности остовного дерева
• Алгоритм Кинг
• Алгоритм Тарьяна поиска LCA за O(1) в оффлайн

Источники информации

• Komlós, J. Linear verification for spanning trees. Combinatorica 5, 57–65 (1985). https://doi.org/10.1007/BF02579443