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

Формально дерево Гомори-Ху 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).

Для более полного понимания определения рассмотрим следующий пример: на иллюстрации представлены неориентированный граф и соответствующее дерево Гомори-Ху. Возьмем пару вершин, например, вершины 3 и 5. Очевидно, что ребро (6, 5) с весом 3 является ребром минимального веса на пути между вершинами 3 и 5 в дереве Гомори-Ху. Легко заметить, что в исходном графе <math>\lambda (s, t) = 3 \;</math>. Удаление этого ребра дает в результате биразбиение вершин ({1, 2, 3, 6}, {4, 5}), являющееся разрезом исходного графа размера 3.

Все предыдущие алгоритмы построения деревьев Гомори-Ху в неориентированных графах использовали подпрограммы нахождения максимального потока. Гомори и Ху показали, как вычислить динамическое дерево 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.

'''Теорема 1. Пусть G = (V, E) – простой невзвешенный граф, имеющий m ребер и n вершин. Тогда дерево Гомори=Ху для графа G можно построить за ожидаемое время <math>\tilde{O} (mn)</math>'''

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

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