4551
правка
Деревья Гомори-Ху: различия между версиями
Материал из WEGA
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 32: | Строка 32: | ||
Теорема 1. Пусть G = (V, E) – простой невзвешенный граф, имеющий m ребер и n вершин. Тогда дерево Гомори=Ху для графа G можно построить за ожидаемое время O | '''Теорема 1. Пусть G = (V, E) – простой невзвешенный граф, имеющий m ребер и n вершин. Тогда дерево Гомори=Ху для графа G можно построить за ожидаемое время <math>\tilde{O} (mn)</math>''' | ||
Скорость их алгоритма всегда на коэффициент Q{n219) (полилогарифмические сомножители n в 6-нотации игнорируются) выше, чем у предыдущей самой быстрой версии алгоритма. | Скорость их алгоритма всегда на коэффициент Q{n219) (полилогарифмические сомножители n в 6-нотации игнорируются) выше, чем у предыдущей самой быстрой версии алгоритма. | ||
Вместо подпрограмм нахождения максимального потока они использовали алгоритм связности по Штейнеру. Связность по Штейнеру множества вершин S (называемого множеством Штейнера) в неориентированном графе представляет собой минимальный размер разреза, разделяющего S на две части; такой разрез называется минимальным разрезом Штейнера. Обобщая алгоритм упаковки дерева, предложенный Габовым [4], для целей нахождения реберной связности графа, Коул и Харинаран [3] предложили алгоритм нахождения связности k по Штейнеру для множества вершин в неориентированных или ориентированных невзвешенных Эйлеровых графах за время O | Вместо подпрограмм нахождения максимального потока они использовали алгоритм связности по Штейнеру. Связность по Штейнеру множества вершин S (называемого множеством Штейнера) в неориентированном графе представляет собой минимальный размер разреза, разделяющего S на две части; такой разрез называется минимальным разрезом Штейнера. Обобщая алгоритм упаковки дерева, предложенный Габовым [4], для целей нахождения реберной связности графа, Коул и Харинаран [3] предложили алгоритм нахождения связности k по Штейнеру для множества вершин в неориентированных или ориентированных невзвешенных Эйлеровых графах за время <math>\tilde{O} (mk^2) \; </math>. (Время исполнения в случае неориентированных графов несколько меньше – <math>\tilde{O}(m + nk^3) \; </math>.) Балгат и коллеги улучшили этот результат, предложив следующую теорему. | ||
'''Теорема 2. В неориентированном или ориентированном невзвешенном Эйлеровом графе связность k по Штейнеру для множества вершин может быть определена за время <math>\tilde{O} (mk) \; </math>.''' | |||
Харихаран и коллеги [9] использовали алгоритм из [3] для разработки алгоритма с ожидаемым временем исполнения O{m + nk3) для вычисления частичного дерева Гомори-Ху для представления значений <math>\lambda (s, t) \;</math> для всех пар вершин s и t, удовлетворяющих условию <math>\lambda (s, t) \le k \;</math>. Замена алгоритма из [3] новым алгоритмом вычисления связности по Штейнеру позволяет вычислить частичное дерево Гомори-Ху за ожидаемое время O(m + nk2). Балгат и коллеги показали, что при помощи более детального анализа этот результат можно улучшить, предложив следующую теорему. | |||
Теорема 3. Частичное дерево Гомори-Ху для невзвешенного неориентированного графа для представления всех значений <math>\lambda (s, t) \;</math>, не превышающих k, может быть построено за ожидаемое время <math>\tilde{O} (mk)</math>. | |||
Поскольку <math>\lambda (s, t) < n \;</math> для всех пар вершин s и t в невзвешенном простом графе, из объявления k равным n в теореме 3 следует справедливость теоремы 1. | |||
== Применение == | == Применение == | ||
