4551
правка
Деревья Гомори-Ху: различия между версиями
Перейти к навигации
Перейти к поиску
→Постановка задачи
Irina (обсуждение | вклад) м (→Литература) |
Irina (обсуждение | вклад) |
||
| Строка 4: | Строка 4: | ||
== Постановка задачи == | == Постановка задачи == | ||
Пусть G = (V, E) – неориентированный граф, в котором |V| = n и |E| = m. Реберная связность двух вершин s, t | Пусть G = (V, E) – неориентированный граф, в котором |V| = n и |E| = m. Реберная связность двух вершин <math>s, t \in V \;</math> , обозначаемая как <math>\lambda (s, t) \;</math> , равняется размеру наименьшего разреза, который разделяет s и t; такой разрез называется минимальным s-t-разрезом. Очевидно, что значения X(s, t) для всех пар вершин s и t можно представить в таблице размера O(n2). Однако из соображений эффективности лучше выбрать более сжатое представление всех значений X(s, t). Деревья Гомори-Ху, также известные как динамические деревья, представляют собой такое сжатое представление линейного (то есть O(n)) объема и с константным (то есть O(1)) временем просмотра. Они имеют еще одно преимущество: помимо представления всех значений X(s, t), они также содержат структурную информацию, на основании которой для любой пары вершин s и t легко может быть получен минимальный s-t-разрез. | ||
| Строка 26: | Строка 26: | ||
Любой подход к построению дерева Гомори-Ху, основанный на нахождении максимального потока, будет исполняться за время, в (n – 1) раз большее времени единичного вычисления максимального потока. До сих пор все более быстрые алгоритмы построения деревьев Гомори-Ху были побочными продуктами более быстрых алгоритмов нахождения максимального потока. Самый быстрый на данный момент алгоритм нахождения максимального потока с временем O{m + n\(s, t)) (полилогарифмические сомножители n в 6-нотации игнорируются), авторами которого были Каргер и Левайн [10], дает наилучшее ожидаемое время исполнения для алгоритма построения дерева Гомори-Ху на простых неориентированных графах с n вершинами, равное 6(и3). Балгат и коллеги [2] улучшили эту временную сложность до 6(mn). Заметим, что оба вышеупомянутых алгоритма являются рандомизированными алгоритмами Лас-Вегаса. Самый быстрый детерминированный алгоритм для задачи построения дерева Гомори-Ху является побочным продуктом алгоритма нахождения максимального потока Голдберга-Рао [5] и имеет время исполнения 6(nm112 min(m; n3/2)). | Любой подход к построению дерева Гомори-Ху, основанный на нахождении максимального потока, будет исполняться за время, в (n – 1) раз большее времени единичного вычисления максимального потока. До сих пор все более быстрые алгоритмы построения деревьев Гомори-Ху были побочными продуктами более быстрых алгоритмов нахождения максимального потока. Самый быстрый на данный момент алгоритм нахождения максимального потока с временем O{m + n\(s, t)) (полилогарифмические сомножители n в 6-нотации игнорируются), авторами которого были Каргер и Левайн [10], дает наилучшее ожидаемое время исполнения для алгоритма построения дерева Гомори-Ху на простых неориентированных графах с n вершинами, равное 6(и3). Балгат и коллеги [2] улучшили эту временную сложность до 6(mn). Заметим, что оба вышеупомянутых алгоритма являются рандомизированными алгоритмами Лас-Вегаса. Самый быстрый детерминированный алгоритм для задачи построения дерева Гомори-Ху является побочным продуктом алгоритма нахождения максимального потока Голдберга-Рао [5] и имеет время исполнения 6(nm112 min(m; n3/2)). | ||
== Основные результаты == | == Основные результаты == | ||