29
правок
Изменения
м
Нет описания правки
|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>, что и требовалось показать.
Предположим, что существует единственное ребро в <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>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> операций сравнения для нахождения ребра с максимальным весом из двух половин.
