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

Материал из Викиконспекты
Версия от 16:04, 25 января 2022; VerlorenMind (обсуждение | вклад) (Перемещение части об алгоритме Комлоса в отдельную статью)
Перейти к: навигация, поиск
Эта статья находится в разработке!

Алгоритм Кинг — алгоритм, предложенный Валери Кинг (англ. Valerie King), позволяющий свести проверку минимальности остовного дерева графа к случаю полного ветвящегося дерева. Данное вспомогательное дерево может быть использовано в частном случае алгоритма Комлоса, для которого также была предложена эффективная реализация, позволяющая выполнить проверку минимальности за линейное время. Алгоритм имеет линейную сложность, что является преимуществом по сравнению с ранними подходами[1][2][3].

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

Пусть [math]T = (V_T, E_T)[/math] — остовное дерево неориентированного взвешенного графа [math]G = (V_G, E_G)[/math]. Проверка минимальности остовного дерева заключается в проверке критерия Тарьяна:

Утверждение:
Остовное дерево является минимальным тогда и только тогда, когда вес любого ребра графа, соединяющего вершины [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]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]

Использование вспомогательного дерева

Построенное вспомогательное дерево позволяет свести задачу проверки минимального остовного дерева к случаю полного ветвящегося дерева, что является частным случаем алгоритма Комлоса верификации минимального остовного дерева. Кинг была предложена эффективная реализация данного случая с использованием битового сжатия, позволяющая проверить минимальность остовного дерева со сложностью [math]O(|E_T|+|V_T|)[/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. ↑ 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=82173»