4551
правка
Деревья Гомори-Ху: различия между версиями
Материал из WEGA
→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 19: | Строка 19: | ||
Для более полного понимания определения рассмотрим следующий пример: на иллюстрации представлены неориентированный граф и соответствующее дерево Гомори-Ху. Возьмем пару вершин, например, вершины 3 и 5. Очевидно, что ребро (6, 5) с весом 3 является ребром минимального веса на пути между вершинами 3 и 5 в дереве Гомори-Ху. Легко заметить, что в исходном графе | Для более полного понимания определения рассмотрим следующий пример: на иллюстрации представлены неориентированный граф и соответствующее дерево Гомори-Ху. Возьмем пару вершин, например, вершины 3 и 5. Очевидно, что ребро (6, 5) с весом 3 является ребром минимального веса на пути между вершинами 3 и 5 в дереве Гомори-Ху. Легко заметить, что в исходном графе <math>\lambda (s, t) = 3 \;</math>. Удаление этого ребра дает в результате биразбиение вершин ({1, 2, 3, 6}, {4, 5}), являющееся разрезом исходного графа размера 3. | ||
Неочевидно, что подобные деревья Гомори-Ху существуют для всех неориентированных графов. Однако в своей классической работе 1961 года Гомори и Ху показали [7], что такие деревья не просто существуют для всех неориентированных графов, но и могут быть вычислены с использованием n – 1 операций вычисления минимальных s-t-разрезов (которые эквивалентны вычислениям максимального потока, согласно знаменитой теореме Менгера). Фактически граф может иметь несколько деревьев Гомори-Ху. | Неочевидно, что подобные деревья Гомори-Ху существуют для всех неориентированных графов. Однако в своей классической работе 1961 года Гомори и Ху показали [7], что такие деревья не просто существуют для всех неориентированных графов, но и могут быть вычислены с использованием n – 1 операций вычисления минимальных s-t-разрезов (которые эквивалентны вычислениям максимального потока, согласно знаменитой теореме Менгера). Фактически граф может иметь несколько деревьев Гомори-Ху. | ||
