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

Перейти к навигации Перейти к поиску
Нет описания правки
Строка 4: Строка 4:


== Постановка задачи ==
== Постановка задачи ==
Пусть 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-разрез.
Пусть 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 можно представить в таблице размера <math>O(n^2) \; </math>. Однако из соображений эффективности лучше выбрать более сжатое представление всех значений <math>\lambda (s, t) \;</math>. Деревья Гомори-Ху, также известные как [[динамические деревья]], представляют собой такое сжатое представление линейного (то есть O(n)) объема и с константным (то есть O(1)) временем просмотра. Они имеют еще одно преимущество: помимо представления всех значений <math>\lambda (s, t) \;</math>, они также содержат структурную информацию, на основании которой для любой пары вершин s и t легко может быть получен минимальный s-t-разрез.




Деревья Гомори-Ху, рис. 1
[[Файл:GomoryHuTree.jpg]]
 
Неориентированный граф (слева) и соответствующее дерево Гомори-Ху (справа)
Неориентированный граф (слева) и соответствующее дерево Гомори-Ху (справа)


Строка 18: Строка 19:




Для более полного понимания определения рассмотрим следующий пример: На рис. 1 представлены неориентированный граф и соответствующее дерево Гомори-Ху. Возьмем пару вершин, например, вершины 3 и 5. Очевидно, что ребро (6, 5) с весом 3 является ребром минимального веса на пути между вершинами 3 и 5 в дереве Гомори-Ху. Легко заметить, что в исходном графе A(3, 5) = 3. Удаление этого ребра дает в результате биразбиение вершин (f1;2; 3; 6g; f4; 5g), являющееся разрезом исходного графа размера 3.
Для более полного понимания определения рассмотрим следующий пример: на иллюстрации представлены неориентированный граф и соответствующее дерево Гомори-Ху. Возьмем пару вершин, например, вершины 3 и 5. Очевидно, что ребро (6, 5) с весом 3 является ребром минимального веса на пути между вершинами 3 и 5 в дереве Гомори-Ху. Легко заметить, что в исходном графе A(3, 5) = 3. Удаление этого ребра дает в результате биразбиение вершин (f1;2; 3; 6g; f4; 5g), являющееся разрезом исходного графа размера 3.


Неочевидно, что подобные деревья Гомори-Ху существуют для всех неориентированных графов. Однако в своей классической работе 1961 года Гомори и Ху показали [7], что такие деревья не просто существуют для всех неориентированных графов, но и могут быть вычислены с использованием n – 1 операций вычисления минимальных s-t-разрезов (которые эквивалентны вычислениям максимального потока, согласно знаменитой теореме Менгера). Фактически граф может иметь несколько деревьев Гомори-Ху.
Неочевидно, что подобные деревья Гомори-Ху существуют для всех неориентированных графов. Однако в своей классической работе 1961 года Гомори и Ху показали [7], что такие деревья не просто существуют для всех неориентированных графов, но и могут быть вычислены с использованием n – 1 операций вычисления минимальных s-t-разрезов (которые эквивалентны вычислениям максимального потока, согласно знаменитой теореме Менгера). Фактически граф может иметь несколько деревьев Гомори-Ху.
4551

правка

Навигация