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

Пусть G = (V, E) – неориентированный граф, в котором |V| = n и |E| = m. Реберная связность двух вершин <math>s, t \in V \;</math> , обозначаемая как <math>\lambda (s, t) \;</math> , равняется размеру наименьшего разреза, который разделяет s и t; такой разрез называется минимальным s-t-разрезом. Очевидно, что значения <math>\lambda (s, t) \;</math> для всех пар вершин s и t можно представить в таблице размера O(n2). Однако из соображений эффективности лучше выбрать более сжатое представление всех значений <math>\lambda (s, t) \;</math>. Деревья Гомори-Ху, также известные как динамические деревья, представляют собой такое сжатое представление линейного (то есть O(n)) объема и с константным (то есть O(1)) временем просмотра. Они имеют еще одно преимущество: помимо представления всех значений <math>\lambda (s, t) \;</math>, они также содержат структурную информацию, на основании которой для любой пары вершин s и t легко может быть получен минимальный s-t-разрез.

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

Харихаран и коллеги [9] использовали алгоритм из [3] для разработки алгоритма с ожидаемым временем исполнения O{m + nk3) для вычисления частичного дерева Гомори-Ху для представления значений <math>\lambda (s, t) \;</math> для всех пар вершин s и t, удовлетворяющих условию <math>\lambda (s, t) \;</math> < k. Замена алгоритма из [3] новым алгоритмом вычисления связности по Штейнеру позволяет вычислить частичное дерево Гомори-Ху за ожидаемое время O(m + nk2). Балгат и коллеги показали, что при помощи более детального анализа этот результат можно улучшить, предложив следующую теорему.

Теорема 3. Частичное дерево Гомори-Ху для невзвешенного неориентированного графа для представления всех значений <math>\lambda (s, t) \;</math>, не превышающих k, может быть построено за ожидаемое время O(mk).

Поскольку <math>\lambda (s, t) \;</math> < n для всех пар вершин s и t в невзвешенном простом графе, из объявления k равным n в теореме 3 следует справедливость теоремы 1.