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

Пусть 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-разрез.

[[Файл:GomoryHuTree.jpg]]

 

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