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

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

Алгоритм Кинг — метод проверки, является ли остовное дерево неориентированного взвешенного графа минимальным. Алгоритм имеет линейную сложность, что является преимуществом по сравнению с ранними подходами[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_2),\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
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Алгоритм_Кинг&oldid=82164»