29
правок
Изменения
Первая версия статьи
{{в разработке}}
'''Алгоритм Кинг''' {{---}} метод проверки, является ли [[Лемма о безопасном ребре#Необходимые определения | остовное дерево]] неориентированного взвешенного графа [[Лемма о безопасном ребре#Необходимые определения |минимальным]]. Алгоритм имеет линейную сложность, что является преимуществом по сравнению с ранними подходами<ref name="tarjan">Tarjan, R.E., 1979. Applications of path compression on balanced trees. Journal of the ACM (JACM), 26(4), pp.690-715.</ref><ref name="drt">B. Dixon, M. Rauch, and R. Tarjan, Verification and sensitivity analysis of minimum spanning trees in linear time,SIAM J. Comput.,21(6) (1992), 1184–1192.</ref><ref name="komlos">Komlós, J. Linear verification for spanning trees. Combinatorica 5, 57–65 (1985). https://doi.org/10.1007/BF02579443</ref>.
== Описание алгоритма ==
Пусть <math>T = (V_T, E_T)</math> {{---}} остовное дерево неориентированного взвешенного графа <math>G = (V_G, E_G)</math>. Обозначим как <math>\{u, v\}</math> ребро, которое соединяет вершины <math>u</math> и <math>v</math>.
Описываемый метод заключается в проверке [[Критерий Тарьяна минимальности остовного дерева|критерия Тарьяна]]:
{{Утверждение
|statement=
Остовное дерево является минимальным тогда и только тогда, когда вес любого ребра графа <math>\{u, v\}</math>, не входящего в остовное дерево, больше либо равен весу ребра, имеющего максимальный вес среди ребер входящих в путь между <math>u</math> и <math>v</math> в остовном дереве.
}}
Используем следующие обозначения:
* <math>T(u, v)</math> {{---}} множество рёбер, входящих в путь между вершинами <math>u, v</math> в дереве <math>T</math>,
* <math>w(e)</math> {{---}} вес ребра <math>e</math>,
* <math>Heavy(T, u, v) = \arg\max\{w(e) | e\in T(u, v)\}</math> {{---}} ребро с максимальным весом на пути между вершинами <math>u, v</math> в дереве <math>T</math>.
Если найти <math>Heavy(T, u, v)</math> для всех <math>u, v \in V_T</math>, то для проверки минимальности остовного дерева достаточно сравнить <math>w(Heavy(T, u, v))</math> и <math>w(\{u, v\})</math> для всех рёбер <math>\{u, v\} \in E_G \setminus E_T</math>.
=== Построение вспомогательного дерева ===
Алгоритм строит вспомогательное дерево <math>B = (V_B, E_B)</math>, являющееся подвешенным и полным ветвящимся (такое дерево, у вершин которого либо 0, либо 2 и более потомка, и в котором все листья находятся на одном уровне), для которого будет выполняться следующее: <math>w(Heavy(B, u, v)) = w(Heavy(T, u, v))</math> для любой пары вершин <math>u, v \in V_T</math>. Построение дерева <math>B</math> основано на [[Алгоритм Борувки|алгоритме Борувки]]. При инициализации алгоритма для каждой вершины <math>v \in T</math> создается лист <math>f(v)</math> в <math>B</math>. Пусть на некотором шаге алгоритма Борувки алгоритм объединяет множество деревьев <math>A</math> в одно дерево, обозначаемое <math>t</math>. При этом алгоритм выбирает некоторые рёбра с наименьшим весом, прилегающие к деревьям из множества <math>A</math>. Обозначим такое ребро для некоторого дерева <math>a \in A</math> как <math>adj(a)</math>. Тогда алгоритм создает новую вершину <math>f(t)</math> в <math>V_B</math> и добавляет новые рёбра в <math>E_B</math> как <math>\{\{f(t), f(a)\} | a \in A\}</math>. Каждому ребру <math>\{f(t), f(a)\}</math> присваивается вес выбранного алгоритмом Борувки ребра, т.е. <math>w(\{f(t), f(a)\}) := w(adj(a))</math>.
Сложность каждой фазы алгоритма пропорциональна количеству рёбер, не выбранных ранее. Так как <math>T</math> является деревом, количество таких рёбер равно количеству деревьев на шаге алгоритма минус один. После каждой фазы количество деревьев сокращается как минимум вдвое, поэтому можно заключить, что построение дерева <math>B</math> имеет сложность <math>O(n)</math>.
{{Теорема
|author=1
|statement=
Пусть <math>T = (V_T, E_T)</math> {{---}} остовное дерево графа, и <math>B = (V_B, E_B)</math> {{---}} дерево, построенное алгоритмом, описанным выше. Тогда для каждой пары вершин <math>x, y \in V_T</math>, <math>w(Heavy(T, x, y)) = w(Heavy(B, f(x), f(y)))</math>.
|proof=
Вначале покажем, что для каждого ребра <math>e \in B(f(x), f(y))</math> существует ребро <math>e'\in T(x,y)</math> для которого верно <math>w(e) \leq w(e')</math>.
Пусть <math>e = \{a, b\}</math> и, без потери общности, положим, что вершина <math>a</math> находится дальше от корня дерева <math>B</math>, чем <math>b</math>. Тогда <math>a = f(t)</math> для некоторого дерева <math>t</math>, построенного для <math>T</math> на некотором шаге алгоритма Борувки, которое содержит либо <math>x</math>, либо <math>y</math>, но не обе вершины одновременно.
Пусть <math>e' \in T(x, y)</math> {{---}} ребро, содержащее ровно одно окончание в дереве <math>t</math>. Так как во время фазы, в которой производился выбор ребра для дерева <math>t</math>, была возможность выбрать ребро <math>e'</math>, его вес <math>w(e') \geq w(e)</math>, что и требовалось показать.
Остается доказать следующее:
{{Утверждение
|statement=
Пусть ребро <math>e \in T(x,y)</math> имеет максимальный вес. Тогда существует ребро в <math>B(f(x), f(y))</math>, имеющее такой же вес.
}}
Предположим, что существует единственное ребро в <math>T(x, y)</math>, имеющее максимальный вес. Доказательство тривиально обобщается на случай нескольких рёбер с максимальным весом.
Если ребро <math>e</math> было выбрано алгоритмом Борувки для дерева, которое содержит <math>x</math> или <math>y</math>, тогда ребру в <math>B(f(x), f(y))</math> был присвоен вес <math>w(e)</math>. Предположим обратное {{---}} ребро <math>e</math> было выбрано алгоритмом для дерева, не содержащего вершины <math>x</math> или <math>y</math>. Одно из окончаний ребра <math>e</math> находится в этом дереве, и данная вершина является промежуточной на пути из <math>x</math> в <math>y</math>. Следовательно, это ребро прилегает к двум другим рёбрам, находящимся на пути из <math>x</math> в <math>y</math>. Тогда среди этих трёх рёбер <math>e</math> является ребром с наибольшим весом, которое не было выбрано, что является противоречием.
}}
=== Применение алгоритма Комлоса к вспомогательному дереву ===
Для полного ветвящегося дерева Комлосом был показан алгоритм<ref name="komlos">Komlós, J. Linear verification for spanning trees. Combinatorica 5, 57–65 (1985). https://doi.org/10.1007/BF02579443</ref>, который находит ребро с максимальным весом на пути для каждой пары вершин, используя <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_1),\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>A(v)</math>, достаточно сравнить веса рёбер из <math>A(s)</math> с весом ребра <math>\{v, s\}</math>. Данное сравнение можно эффективно выполнить с помощью двоичного поиска. Итоговое множество <math>A(v)</math> получается путем объединением множеств рёбер, полученных для каждого потомка.
Комлос показал, что <math>\sum\limits_{v\in T} \log |A(v)| = O\left(|V_T|\log\left(\frac{|E_T|+|V_T|}{|V_T|}\right)\right)</math><ref name="komlos">Komlós, J. Linear verification for spanning trees. Combinatorica 5, 57–65 (1985). https://doi.org/10.1007/BF02579443</ref>, что дает верхнюю границу для количества операций сравнений, используемых алгоритмом.
== Особенности реализации алгоритма ==
=== Используемые структуры данных ===
Реализация алгоритма требует операций над битовыми словами размера порядка <math>O(\log|V_T|)</math>. Было показано, что рассматриваемые операции возможно предпосчитать за время <math>O(|V_T|)</math> и сохранить в таблице, обращение к которой занимает <math>O(1)</math> операций. Алгоритм пользуется структурами данных, описанными ниже.
Вершины во вспомогательном дереве нумеруются битовыми словами следующим образом:
# Каждый лист помечается порядковым номером 0, 1, 2... в двоичном представлении в порядке встречи листов при [[Обход_в_глубину,_цвета_вершин|обходе в глубину]].
# Каждый не-лист помечается номером своего потомка, содержащим наибольшее количество ведущих нулей.
Рёбра в дереве получают тег, который формируется следующим образом. Рассмотрим ребро <math>e = \{u, v\}</math>, где <math>v</math> находится дальше от корня. Пусть <math>d(v)</math> обозначает расстояние от вершины <math>v</math> до корня, а <math>i(v)</math> {{---}} номер младшей единицы в номере вершины <math>v</math>. Тогда тег ребра <math>e</math> {{---}} строка размера <math>\lceil\lg\lg |V_T|\rceil</math>, записанная как <math><d(v), i(v)></math>. В оригинальной работе было показано, что имея тег ребра и номер вершины, можно обнаружить ребро в графе за константное время.
Для каждой вершины <math>v</math> создается вектор длины <math>\lceil\lg|V_T|\rceil</math>, обозначаемый как <math>LCA(v)</math>, чей бит с номером i равен 1, когда существует путь из листа в поддереве с корнем <math>v</math> в лист в другом поддереве, наивысшая по уровню вершина которого (иначе говоря, наименьший общий предок двух листьев) находится на расстоянии <math>i</math> от <math>v</math>.
Далее, вершины делятся на два класса. Если <math>|A(v)|>\frac{\lceil\lg|V_T|\rceil}{\lceil\lg\lg |V_T|\rceil}</math>, то вершина <math>v</math> считается ''большой''; в противном случае вершина считается ''малой''. Для больших вершин создаются списки <math>bigList</math>, для малых {{---}} <math>smallList</math>. <math>BigList</math> содержит теги рёбер из <math>A(v)</math> в порядке неубывания длин путей из корня в листья, соответствующих рёбрам. Для хранения такого списка требуется <math>\frac{|A(v)|\lceil\lg\lg |V_T|\rceil}{\lceil\lg|V_T|\rceil}=O(\log\log |V_T|)</math> памяти.
Для малой вершины <math>v</math> обозначим за <math>a</math> ближайшего большого предка. Список <math>smallList</math> содержит либо теги рёбер из <math>A(v)</math>, либо, если ребро <math>e</math> из <math>A(v)</math> содержится в интервале от корня до <math>a</math>, указатель на <math>bigList</math> вершины <math>a</math>, содержащий тег для <math>e</math>. Для каждой малой вершины запоминается номер первого элемента в <math>smallList</math>, являющимся тегом. Элементы списка, идущие после первого тега, тоже являются тегами. Для хранения <math>smallList</math> требуется одно битовое слово.
Построение и использование структуры данных подробно описано в оригинальной статье.
=== Анализ сложности ===
Было показано, что сложность построения данных для одной вершины <math>v</math> возможно за <math>O\left(\log |A(v)|\right)</math> операций. Суммируя по всем вершинам, итоговая сложность алгоритма <math>O\left(|V_T|\log\left(\frac{|E_T|+|V_T|}{|V_T|}\right)\right)</math>, что и было показано Комлосом.
Дополнительно алгоритм тратит <math>O(|V_T|+|E_T|)</math> операций для построения списков <math>LCA(v)</math>, <math>O(n)</math> операций для обработки таблиц с предвычисленными значениями и <math>O(m)</math> операций сравнения для нахождения ребра с максимальным весом из двух половин.
В завершении алгоритма, требуется сравнить веса рёбер графа, которые не входят в остовное дерево, с найденными в дереве <math>B</math> рёбрами наибольшего веса, что потребует дополнительных <math>O(m)</math> операций сравнения.
== Источники информации ==
* King, V. A simpler minimum spanning tree verification algorithm. Algorithmica 18, 263–270 (1997). https://doi.org/10.1007/BF02526037
== Примечания ==
<references/>
'''Алгоритм Кинг''' {{---}} метод проверки, является ли [[Лемма о безопасном ребре#Необходимые определения | остовное дерево]] неориентированного взвешенного графа [[Лемма о безопасном ребре#Необходимые определения |минимальным]]. Алгоритм имеет линейную сложность, что является преимуществом по сравнению с ранними подходами<ref name="tarjan">Tarjan, R.E., 1979. Applications of path compression on balanced trees. Journal of the ACM (JACM), 26(4), pp.690-715.</ref><ref name="drt">B. Dixon, M. Rauch, and R. Tarjan, Verification and sensitivity analysis of minimum spanning trees in linear time,SIAM J. Comput.,21(6) (1992), 1184–1192.</ref><ref name="komlos">Komlós, J. Linear verification for spanning trees. Combinatorica 5, 57–65 (1985). https://doi.org/10.1007/BF02579443</ref>.
== Описание алгоритма ==
Пусть <math>T = (V_T, E_T)</math> {{---}} остовное дерево неориентированного взвешенного графа <math>G = (V_G, E_G)</math>. Обозначим как <math>\{u, v\}</math> ребро, которое соединяет вершины <math>u</math> и <math>v</math>.
Описываемый метод заключается в проверке [[Критерий Тарьяна минимальности остовного дерева|критерия Тарьяна]]:
{{Утверждение
|statement=
Остовное дерево является минимальным тогда и только тогда, когда вес любого ребра графа <math>\{u, v\}</math>, не входящего в остовное дерево, больше либо равен весу ребра, имеющего максимальный вес среди ребер входящих в путь между <math>u</math> и <math>v</math> в остовном дереве.
}}
Используем следующие обозначения:
* <math>T(u, v)</math> {{---}} множество рёбер, входящих в путь между вершинами <math>u, v</math> в дереве <math>T</math>,
* <math>w(e)</math> {{---}} вес ребра <math>e</math>,
* <math>Heavy(T, u, v) = \arg\max\{w(e) | e\in T(u, v)\}</math> {{---}} ребро с максимальным весом на пути между вершинами <math>u, v</math> в дереве <math>T</math>.
Если найти <math>Heavy(T, u, v)</math> для всех <math>u, v \in V_T</math>, то для проверки минимальности остовного дерева достаточно сравнить <math>w(Heavy(T, u, v))</math> и <math>w(\{u, v\})</math> для всех рёбер <math>\{u, v\} \in E_G \setminus E_T</math>.
=== Построение вспомогательного дерева ===
Алгоритм строит вспомогательное дерево <math>B = (V_B, E_B)</math>, являющееся подвешенным и полным ветвящимся (такое дерево, у вершин которого либо 0, либо 2 и более потомка, и в котором все листья находятся на одном уровне), для которого будет выполняться следующее: <math>w(Heavy(B, u, v)) = w(Heavy(T, u, v))</math> для любой пары вершин <math>u, v \in V_T</math>. Построение дерева <math>B</math> основано на [[Алгоритм Борувки|алгоритме Борувки]]. При инициализации алгоритма для каждой вершины <math>v \in T</math> создается лист <math>f(v)</math> в <math>B</math>. Пусть на некотором шаге алгоритма Борувки алгоритм объединяет множество деревьев <math>A</math> в одно дерево, обозначаемое <math>t</math>. При этом алгоритм выбирает некоторые рёбра с наименьшим весом, прилегающие к деревьям из множества <math>A</math>. Обозначим такое ребро для некоторого дерева <math>a \in A</math> как <math>adj(a)</math>. Тогда алгоритм создает новую вершину <math>f(t)</math> в <math>V_B</math> и добавляет новые рёбра в <math>E_B</math> как <math>\{\{f(t), f(a)\} | a \in A\}</math>. Каждому ребру <math>\{f(t), f(a)\}</math> присваивается вес выбранного алгоритмом Борувки ребра, т.е. <math>w(\{f(t), f(a)\}) := w(adj(a))</math>.
Сложность каждой фазы алгоритма пропорциональна количеству рёбер, не выбранных ранее. Так как <math>T</math> является деревом, количество таких рёбер равно количеству деревьев на шаге алгоритма минус один. После каждой фазы количество деревьев сокращается как минимум вдвое, поэтому можно заключить, что построение дерева <math>B</math> имеет сложность <math>O(n)</math>.
{{Теорема
|author=1
|statement=
Пусть <math>T = (V_T, E_T)</math> {{---}} остовное дерево графа, и <math>B = (V_B, E_B)</math> {{---}} дерево, построенное алгоритмом, описанным выше. Тогда для каждой пары вершин <math>x, y \in V_T</math>, <math>w(Heavy(T, x, y)) = w(Heavy(B, f(x), f(y)))</math>.
|proof=
Вначале покажем, что для каждого ребра <math>e \in B(f(x), f(y))</math> существует ребро <math>e'\in T(x,y)</math> для которого верно <math>w(e) \leq w(e')</math>.
Пусть <math>e = \{a, b\}</math> и, без потери общности, положим, что вершина <math>a</math> находится дальше от корня дерева <math>B</math>, чем <math>b</math>. Тогда <math>a = f(t)</math> для некоторого дерева <math>t</math>, построенного для <math>T</math> на некотором шаге алгоритма Борувки, которое содержит либо <math>x</math>, либо <math>y</math>, но не обе вершины одновременно.
Пусть <math>e' \in T(x, y)</math> {{---}} ребро, содержащее ровно одно окончание в дереве <math>t</math>. Так как во время фазы, в которой производился выбор ребра для дерева <math>t</math>, была возможность выбрать ребро <math>e'</math>, его вес <math>w(e') \geq w(e)</math>, что и требовалось показать.
Остается доказать следующее:
{{Утверждение
|statement=
Пусть ребро <math>e \in T(x,y)</math> имеет максимальный вес. Тогда существует ребро в <math>B(f(x), f(y))</math>, имеющее такой же вес.
}}
Предположим, что существует единственное ребро в <math>T(x, y)</math>, имеющее максимальный вес. Доказательство тривиально обобщается на случай нескольких рёбер с максимальным весом.
Если ребро <math>e</math> было выбрано алгоритмом Борувки для дерева, которое содержит <math>x</math> или <math>y</math>, тогда ребру в <math>B(f(x), f(y))</math> был присвоен вес <math>w(e)</math>. Предположим обратное {{---}} ребро <math>e</math> было выбрано алгоритмом для дерева, не содержащего вершины <math>x</math> или <math>y</math>. Одно из окончаний ребра <math>e</math> находится в этом дереве, и данная вершина является промежуточной на пути из <math>x</math> в <math>y</math>. Следовательно, это ребро прилегает к двум другим рёбрам, находящимся на пути из <math>x</math> в <math>y</math>. Тогда среди этих трёх рёбер <math>e</math> является ребром с наибольшим весом, которое не было выбрано, что является противоречием.
}}
=== Применение алгоритма Комлоса к вспомогательному дереву ===
Для полного ветвящегося дерева Комлосом был показан алгоритм<ref name="komlos">Komlós, J. Linear verification for spanning trees. Combinatorica 5, 57–65 (1985). https://doi.org/10.1007/BF02579443</ref>, который находит ребро с максимальным весом на пути для каждой пары вершин, используя <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_1),\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>A(v)</math>, достаточно сравнить веса рёбер из <math>A(s)</math> с весом ребра <math>\{v, s\}</math>. Данное сравнение можно эффективно выполнить с помощью двоичного поиска. Итоговое множество <math>A(v)</math> получается путем объединением множеств рёбер, полученных для каждого потомка.
Комлос показал, что <math>\sum\limits_{v\in T} \log |A(v)| = O\left(|V_T|\log\left(\frac{|E_T|+|V_T|}{|V_T|}\right)\right)</math><ref name="komlos">Komlós, J. Linear verification for spanning trees. Combinatorica 5, 57–65 (1985). https://doi.org/10.1007/BF02579443</ref>, что дает верхнюю границу для количества операций сравнений, используемых алгоритмом.
== Особенности реализации алгоритма ==
=== Используемые структуры данных ===
Реализация алгоритма требует операций над битовыми словами размера порядка <math>O(\log|V_T|)</math>. Было показано, что рассматриваемые операции возможно предпосчитать за время <math>O(|V_T|)</math> и сохранить в таблице, обращение к которой занимает <math>O(1)</math> операций. Алгоритм пользуется структурами данных, описанными ниже.
Вершины во вспомогательном дереве нумеруются битовыми словами следующим образом:
# Каждый лист помечается порядковым номером 0, 1, 2... в двоичном представлении в порядке встречи листов при [[Обход_в_глубину,_цвета_вершин|обходе в глубину]].
# Каждый не-лист помечается номером своего потомка, содержащим наибольшее количество ведущих нулей.
Рёбра в дереве получают тег, который формируется следующим образом. Рассмотрим ребро <math>e = \{u, v\}</math>, где <math>v</math> находится дальше от корня. Пусть <math>d(v)</math> обозначает расстояние от вершины <math>v</math> до корня, а <math>i(v)</math> {{---}} номер младшей единицы в номере вершины <math>v</math>. Тогда тег ребра <math>e</math> {{---}} строка размера <math>\lceil\lg\lg |V_T|\rceil</math>, записанная как <math><d(v), i(v)></math>. В оригинальной работе было показано, что имея тег ребра и номер вершины, можно обнаружить ребро в графе за константное время.
Для каждой вершины <math>v</math> создается вектор длины <math>\lceil\lg|V_T|\rceil</math>, обозначаемый как <math>LCA(v)</math>, чей бит с номером i равен 1, когда существует путь из листа в поддереве с корнем <math>v</math> в лист в другом поддереве, наивысшая по уровню вершина которого (иначе говоря, наименьший общий предок двух листьев) находится на расстоянии <math>i</math> от <math>v</math>.
Далее, вершины делятся на два класса. Если <math>|A(v)|>\frac{\lceil\lg|V_T|\rceil}{\lceil\lg\lg |V_T|\rceil}</math>, то вершина <math>v</math> считается ''большой''; в противном случае вершина считается ''малой''. Для больших вершин создаются списки <math>bigList</math>, для малых {{---}} <math>smallList</math>. <math>BigList</math> содержит теги рёбер из <math>A(v)</math> в порядке неубывания длин путей из корня в листья, соответствующих рёбрам. Для хранения такого списка требуется <math>\frac{|A(v)|\lceil\lg\lg |V_T|\rceil}{\lceil\lg|V_T|\rceil}=O(\log\log |V_T|)</math> памяти.
Для малой вершины <math>v</math> обозначим за <math>a</math> ближайшего большого предка. Список <math>smallList</math> содержит либо теги рёбер из <math>A(v)</math>, либо, если ребро <math>e</math> из <math>A(v)</math> содержится в интервале от корня до <math>a</math>, указатель на <math>bigList</math> вершины <math>a</math>, содержащий тег для <math>e</math>. Для каждой малой вершины запоминается номер первого элемента в <math>smallList</math>, являющимся тегом. Элементы списка, идущие после первого тега, тоже являются тегами. Для хранения <math>smallList</math> требуется одно битовое слово.
Построение и использование структуры данных подробно описано в оригинальной статье.
=== Анализ сложности ===
Было показано, что сложность построения данных для одной вершины <math>v</math> возможно за <math>O\left(\log |A(v)|\right)</math> операций. Суммируя по всем вершинам, итоговая сложность алгоритма <math>O\left(|V_T|\log\left(\frac{|E_T|+|V_T|}{|V_T|}\right)\right)</math>, что и было показано Комлосом.
Дополнительно алгоритм тратит <math>O(|V_T|+|E_T|)</math> операций для построения списков <math>LCA(v)</math>, <math>O(n)</math> операций для обработки таблиц с предвычисленными значениями и <math>O(m)</math> операций сравнения для нахождения ребра с максимальным весом из двух половин.
В завершении алгоритма, требуется сравнить веса рёбер графа, которые не входят в остовное дерево, с найденными в дереве <math>B</math> рёбрами наибольшего веса, что потребует дополнительных <math>O(m)</math> операций сравнения.
== Источники информации ==
* King, V. A simpler minimum spanning tree verification algorithm. Algorithmica 18, 263–270 (1997). https://doi.org/10.1007/BF02526037
== Примечания ==
<references/>
