29
правок
Изменения
Перемещение части об алгоритме Комлоса в отдельную статью
{{в разработке}}
'''Алгоритм Кинг''' {{---}} метод проверкиалгоритм, является ли предложенный Валери Кинг (''англ. Valerie King''), позволяющий свести проверку минимальности [[Лемма о безопасном ребре#Необходимые определения | остовное деревоостовного дерева]] неориентированного взвешенного графа к случаю полного ветвящегося дерева. Данное вспомогательное дерево может быть использовано в частном случае [[Лемма о безопасном ребре#Необходимые определения Алгоритм Комлоса|минимальнымалгоритма Комлоса]], для которого также была предложена эффективная реализация, позволяющая выполнить проверку минимальности за линейное время. Алгоритм имеет линейную сложность, что является преимуществом по сравнению с ранними подходами<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, </math> и <math>v\}</math>, не входящего в остовное дерево, больше либо равен весу ребра, имеющего максимальный вес среди ребер входящих в путь между <math>u</math> и <math>v</math> в остовном дереве.
}}
Используем следующие обозначения:
* <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>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>, что и требовалось показать.
Предположим, что существует единственное ребро в <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> является ребром с наибольшим весом, которое не было выбрано, что является противоречием.
}}
== См. также ==
* [[Алгоритм Комлоса]]
* [[Алгоритм Борувки]]
* [[Критерий Тарьяна минимальности остовного дерева]]
== Источники информации ==
* King, V. A simpler minimum spanning tree verification algorithm. Algorithmica 18, 263–270 (1997). https://doi.org/10.1007/BF02526037