Алгоритм Кинг — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
Строка 1: Строка 1:
{| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
 
|+
 
|-align="center"
 
|'''НЕТ ВОЙНЕ'''
 
|-style="font-size: 16px;"
 
|
 
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
 
 
Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
 
 
Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
 
 
Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
 
 
''Антивоенный комитет России''
 
|-style="font-size: 16px;"
 
|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
 
|-style="font-size: 16px;"
 
|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
 
|}
 
 
 
{{в разработке}}
 
{{в разработке}}
  

Текущая версия на 19:32, 4 сентября 2022

Эта статья находится в разработке!

Алгоритм Кинг — алгоритм, предложенный Валери Кинг (англ. 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