Алгоритм Кинг

Материал из Викиконспекты
Перейти к: навигация, поиск
Эта статья находится в разработке!

Алгоритм Кинг — метод проверки, является ли остовное дерево неориентированного взвешенного графа минимальным. Алгоритм имеет линейную сложность, что является преимуществом по сравнению с ранними подходами[1][2][3].

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

Пусть [math]T = (V_T, E_T)[/math] — остовное дерево неориентированного взвешенного графа [math]G = (V_G, E_G)[/math]. Обозначим как [math]\{u, 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]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].

Теорема (1):
Пусть [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].
Доказательство:
[math]\triangleright[/math]

Вначале покажем, что для каждого ребра [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]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]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] является ребром с наибольшим весом, которое не было выбрано, что является противоречием.
[math]\triangleleft[/math]

Применение алгоритма Комлоса к вспомогательному дереву

Для полного ветвящегося дерева Комлосом был показан алгоритм[3], который находит ребро с максимальным весом на пути для каждой пары вершин, используя [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][3], что дает верхнюю границу для количества операций сравнений, используемых алгоритмом.

Особенности реализации алгоритма

Используемые структуры данных

Реализация алгоритма требует операций над битовыми словами размера порядка [math]O(\log|V_T|)[/math]. Было показано, что рассматриваемые операции возможно предпосчитать за время [math]O(|V_T|)[/math] и сохранить в таблице, обращение к которой занимает [math]O(1)[/math] операций. Алгоритм пользуется структурами данных, описанными ниже.

Вершины во вспомогательном дереве нумеруются битовыми словами следующим образом:

  1. Каждый лист помечается порядковым номером 0, 1, 2... в двоичном представлении в порядке встречи листов при обходе в глубину.
  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]\lt d(v), i(v)\gt [/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)|\gt \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] операций сравнения.

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

Примечания

  1. Tarjan, R.E., 1979. Applications of path compression on balanced trees. Journal of the ACM (JACM), 26(4), pp.690-715.
  2. 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.
  3. 3,0 3,1 3,2 Komlós, J. Linear verification for spanning trees. Combinatorica 5, 57–65 (1985). https://doi.org/10.1007/BF02579443