4511
правок
Минимальное остовное дерево: различия между версиями
Перейти к навигации
Перейти к поиску
Минимальное остовное дерево (посмотреть исходный код)
Версия от 19:11, 22 декабря 2015
, 22 декабря 2015→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 52: | Строка 52: | ||
Теорема 2. Пусть G равномерно выбирается случайным образом из множества всех графов, имеющих n вершин и m ребер. Тогда, независимо от весов ребер, MST(G) может быть найдено за время O(m + n) с вероятностью 1 | '''Теорема 2. Пусть G равномерно выбирается случайным образом из множества всех графов, имеющих n вершин и m ребер. Тогда, независимо от весов ребер, MST(G) может быть найдено за время O(m + n) с вероятностью <math>1 - 2^{- \Omega (m / \alpha^2)} \;</math>, где <math>\alpha = \alpha(m, n) \;</math> – медленно растущая обратная функция Аккермана.''' | ||
Теорему 1 можно сопоставить с результатами исследований Карджера, Клейна и Тарьяна [9], а также Шазеля [2], посвященных рандомизированной и детерминированной сложности задачи MST. | |||
'''Теорема 3 [9]. Минимальный остовный лес графа с m ребрами может быть вычислен при помощи рандомизированного алгоритма за время O(m) с вероятностью <math>1 - 2^{- \Omega (m)} \;</math>.''' | |||
Теорема 4 [2]. Минимальное остовное дерево графа может быть вычислено за время O( | |||
'''Теорема 4 [2]. Минимальное остовное дерево графа может быть вычислено за время <math>O(m \alpha(m, n)) \;</math> при помощи детерминированного алгоритма, где <math>\alpha \;</math> – обратная функция Аккермана.''' | |||
== Применение == | == Применение == | ||