4551
правка
Рандомизированный алгоритм нахождения минимального остовного дерева: различия между версиями
Перейти к навигации
Перейти к поиску
м
Рандомизированный алгоритм нахождения минимального остовного дерева (посмотреть исходный код)
Версия от 23:44, 28 апреля 2016
, 28 апреля 2016→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 36: | Строка 36: | ||
'''Лемма 1 (лемма выборки для задачи MST)'''. Пусть <math>H = (v, E_H) \;</math> создан из исходного графа с взвешенными ребрами G = (V, E) посредством включения каждого ребра с вероятностью p, не зависящей от других ребер. Пусть F – минимальный остовный лес H. Тогда ожидаемое количество F-легких дуг в G не превышает n/p. | '''Лемма 1 (лемма выборки для задачи MST)'''. Пусть <math>H = (v, E_H) \;</math> создан из исходного графа с взвешенными ребрами G = (V, E) посредством включения каждого ребра с вероятностью p, не зависящей от других ребер. Пусть F – минимальный остовный лес H. Тогда ожидаемое количество F-легких дуг в G не превышает n/p. | ||
Алгоритм KKT определяет ребра минимального остовного дерева G, используя только шаги Борувки. После каждых двух шагов Борувки он выполняет удаление F-тяжелых ребер, используя минимальный остовный лес F подграфа, полученный посредством выборки ребер с вероятностью p = 1/2. Как упоминалось ранее, эти F-тяжелые ребра могут быть обнаружены за линейное время. Минимальный остовный лес графа-выборки вычисляется рекурсивным образом. | Алгоритм KKT определяет ребра минимального остовного дерева G, используя только шаги Борувки. После каждых двух шагов Борувки он выполняет удаление F-тяжелых ребер, используя минимальный остовный лес F подграфа, полученный посредством выборки ребер с вероятностью p = 1/2. Как упоминалось ранее, эти F-тяжелые ребра могут быть обнаружены за линейное время. Минимальный остовный лес графа-выборки вычисляется рекурсивным образом. | ||