Рандомизированный алгоритм нахождения минимального остовного дерева: различия между версиями

Основным результатом работы [9] является рандомизированный алгоритм нахождения минимального остовного дерева за ожидаемое линейное время. С весами ребер не выполняется никаких других действий, кроме попарных сравнений. Алгоритм не предполагает какого-либо конкретного представления весов ребер (т.е. должны ли их значения быть целыми или вещественными), он только считает, что любое сравнение весов для пары ребер может быть выполнено за единичное время. В статье также показано, что время исполнения алгоритма составляет O(m + n) с экспоненциально высокой вероятностью <math>1 - exp( - \Omega (m)) \;</math>, а время исполнения в наихудшем случае составит O(n + m log n).

Простая и элегантная [[лемма выборки]] для задачи MST, сформулированная в данном случае в виде Леммы 1, явилась основным инструментом вывода и анализа алгоритма для задачи KKT. Перед тем, как сформулировать лемму, напомним пару необходимых определений и фактов:

1. Хорошо известное [[свойство циклов]] для минимальных остовных деревьев заключается в том, что самое тяжелое ребро любого цикла входного графа G ''не может'' входить в состав минимального остовного дерева.

2. Пусть F – лес графа G (т.е. ациклический подграф G). Ребро <math>e \in E \;</math> называется F-легким, если имеет место один из двух случаев: (1) <math>F \cup \{ e \} \;</math> продолжает оставаться лесом графа G; (2) самое тяжелое ребро цикла, содержащего e, не совпадает с e. Ребро G, не являющееся F-легким, называется F-тяжелым. Отметим, что согласно свойству циклов F-тяжелое ребро не может входить в состав минимального остовного дерева G н''езависимо от того, какой лес F используется''. Пусть имеется лес F графа G. Множество F-тяжелых ребер может быть вычислено за линейное время при помощи простой модификации существующих алгоритмов верификации минимального остовного дерева [6, 12].

'''Лемма 1 (лемма выборки для задачи MST)'''. Пусть <math>H = (v, E_H) \;</math> создан из исходного графа с взвешенными ребрами G = (V, E) посредством включения каждого ребра с вероятностью p, не зависящей от других ребер. Пусть F – минимальный остовный лес H. Тогда ожидаемое количество F-легких дуг в G не превышает n/p.

В работе [9] доказываются следующие положения.