Деревья Гомори-Ху: различия между версиями

Формально дерево Гомори-Ху T = (v, F) для неориентированного графа G = (V, E) представляет собой взвешенное неориентированное дерево, определенное на вершинах графа, для которого выполняются следующие свойства:

• Для любой пары вершин <math>s, t \in V \;</math> , <math>\lambda (s, t) \;</math> равно минимальному весу ребра уникального пути, соединяющего s и t в T. Это ребро назовем e(s, t). Если на пути из s к t в T имеется несколько ребер с минимальным весом, любое из этих ребер обозначается как e(s, t).

Все предыдущие алгоритмы построения деревьев Гомори-Ху в неориентированных графах использовали подпрограммы нахождения максимального потока. Гомори и Ху показали, как вычислить динамическое дерево T при помощи n – 1 операций вычисления максимального потока и операций сжатия графа. Гусфилд [8] предложил алгоритм, не использующий операций сокращения графа; все n – 1 операций вычисления максимального потока выполняются на исходном графе. Голдберг и Цюцюликлис [6] выполнили экспериментальное исследование алгоритмов, предложенных Гомори и Ху, а также Гусфилдом, для решения задачи поддержания динамического дерева, и описали эффективные реализации этих алгоритмов. Бенцур [1] привел примеры, демонстрирующие, что динамические деревья с отрезанием не существуют для ориентированных графов.

Любой подход к построению дерева Гомори-Ху, основанный на нахождении максимального потока, будет исполняться за время, в (n – 1) раз большее времени единичного вычисления максимального потока. До сих пор все более быстрые алгоритмы построения деревьев Гомори-Ху были побочными продуктами более быстрых алгоритмов нахождения максимального потока. Самый быстрый на данный момент алгоритм нахождения максимального потока с временем <math>\tilde{O} (m + n \lambda (s, t))</math> (полилогарифмические сомножители n в <math>\tilde{O}</math>-нотации игнорируются), авторами которого были Каргер и Левайн [10], дает наилучшее ожидаемое время исполнения для алгоритма построения дерева Гомори-Ху на простых неориентированных графах с n вершинами, равное <math>\tilde{O} (n^3) \; </math>. Балгат и коллеги [2] улучшили эту временную сложность до <math>\tilde{O} (mn) \; </math>. Заметим, что оба вышеупомянутых алгоритма являются рандомизированными алгоритмами Лас-Вегаса. Самый быстрый детерминированный алгоритм для задачи построения дерева Гомори-Ху является побочным продуктом алгоритма нахождения максимального потока Голдберга-Рао [5] и имеет время исполнения <math>\tilde{O} (nm^{1/2} min(m, n^{3/2}))</math>.

Балгат и коллеги [2] рассматривали задачу создания эффективного алгоритма построения дерева Гомори-Ху на невзвешенных неориентированных графах. Результатом их работы стала теорема 1.

Вместо подпрограмм нахождения максимального потока они использовали алгоритм связности по Штейнеру. Связность по Штейнеру множества вершин S (называемого множеством Штейнера) в неориентированном графе представляет собой минимальный размер разреза, разделяющего S на две части; такой разрез называется минимальным разрезом Штейнера. Обобщая алгоритм упаковки дерева, предложенный Габовым [4], для целей нахождения реберной связности графа, Коул и Харинаран [3] предложили алгоритм нахождения связности k по Штейнеру для множества вершин в неориентированных или ориентированных невзвешенных Эйлеровых графах за время <math>\tilde{O} (mk^2) \; </math>. (Время исполнения в случае неориентированных графов несколько меньше – <math>\tilde{O}(m + nk^3) \; </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>.

Задача дерандомизации алгоритма, предложенного Балгатом и коллегами [2], с целью создания детерминированного алгоритма построения дерева Гомори-Ху на невзвешенных неориентированных графах с временем исполнения <math>\tilde{O} (mn) \; </math> остается открытой. Еще одна нерешенная задача – расширение результатов работы [2] на взвешенные графы.

Голдберг и Цюцюликлис [6] выполнили широкомасштабное экспериментальное исследование алгоритмов, предложенных Гомори и Ху, а также Гусфилдом, для решения задачи поддержания динамического дерева. Они показали варианты эффективной реализации этих алгоритмов, а также предложили и оценили эвристики для ускорения их исполнения. Согласно их наблюдениям, алгоритм Гусфилда во многих ситуациях работает быстрее, зато алгоритм Гомори и Ху более надежен. Более детальное описание результатов экспериментов можно найти в [6].