В комбинаторной оптимизации , то дерево Гомори-Х [1] неориентированный граф с емкостью представляет собой взвешенное дерево , что соответствует минимальному сек - т вырезы для всех х - т пары в графе. Дерево Гомори – Ху можно построить в | V | - 1 расчет максимального расхода .
Определение
Пусть G = (( V G , E G ), c ) - неориентированный граф, где c ( u , v ) - емкость ребра ( u , v ) соответственно.
- Обозначим минимальную емкость в м разреза через Л - й для каждого х , т ∈ V G .
- Пусть Т = ( V G , Е Т ) является деревом, обозначим множество ребер в го пути от Р ст для каждого х , т ∈ V G .
Тогда T называется деревом Гомори – Ху группы G , если для каждого s , t ∈ V G
- λ st = min e∈P st c ( S e , T e ),
где
- S е , Т е ⊆ V G являются две компоненты связности Т ∖ { е }, и , таким образом , ( S е , Т е ) образуют с - т разрез в G .
- с ( S е , Т е ) является способность разреза в G .
Алгоритм
Алгоритм Гомори – Ху
- Вход : взвешенный неориентированный граф G = (( V G , E G ), c )
- Выход : Дерево Гомори – Ху T = ( V T , E T ).
- 1. Положить V T = { V G } и E T = ∅.
- 2. Выберем некоторый X ∈ V T с | X | ≥ 2, если такое X существует. В противном случае переходите к шагу 6.
- 3. Для каждого подключенного компонента C = ( V C , Е С ) в Т ∖ Х . Пусть S C = ∪ V T ∈V C V T . Пусть S = { S C | C - компонента связности в T ∖ X }.
- Сожмите компоненты, чтобы образовать G '= (( V G' , E G ' ), c '), где
- В G» = X ∪ S .
- E G ' = E G | X × X ∪ {( u , S C ) ∈ X × S | ( u , v ) ∈ E G для некоторого v ∈ S C } ∪ {( S C1 , S C2 ) ∈ S × S | ( u , v ) ∈ E G для некоторых u∈ S C1 и v ∈ S C2 }.
- c ': V G' × V G ' → R + - функция емкости, определяемая как,
- если ( u , S C ) ∈ E G | X × S , c '( u , S C ) = Σ v∈S C : (u, v) ∈E G c ( u , v ),
- если ( S C1 , S C2 ) ∈ E G | S × S , c '( S C1 , S C2 ) = Σ (u, v) ∈E G : u∈S C1 ∧v∈S C2 c ( u , v ),
- c '( u , v ) = c ( u , v ) в противном случае.
- 4. Выберите две вершины s , t ∈ X и найдите минимальный s - t разрез ( A ', B ') в G '.
- Положим A = (∪ S C ∈ A '∩ S S C ) ∪ ( A ' ∩ X ) и B = (∪ S C ∈ B '∩ S S C ) ∪ ( B ' ∩ X ).
- 5. Положить V T = ( V T ∖ X ) ∪ { A ∩ X , B ∩ X }.
- Для каждого e = ( X , Y ) ∈ E T do
- Если Y ⊂ A , положим e '= ( A ∩ X , Y ), иначе положим e ' = ( B ∩ X , Y ).
- Положим E T = ( E T ∖ { e }) ∪ { e '} и w ( e ') = w ( e ).
- Положим E T = E T ∪ {( A ∩ X , B ∩ X )}.
- Положим w (( A ∩ X , B ∩ X )) = c '( A ', B ').
- Переходите к шагу 2.
- 6. Заменим каждый { v } ∈ V T на v и каждый ({ u }, { v }) ∈ E T на ( u , v ). Выход Т .
Анализ
Используя субмодулярное свойство функции емкости c , имеем
- c ( X ) + c ( Y ) ≥ c ( X ∩ Y ) + c ( X ∪ Y ).
Тогда можно показать , что минимальная сек - т сокращение G 'также минимальный ы - т сократить в G для любых х , т ∈ X .
Чтобы показать, что для всех ( P , Q ) ∈ E T , w ( P , Q ) = λ pq для некоторых p ∈ P , q ∈ Q на протяжении всего алгоритма, используется следующая лемма
- Для любых i , j , k в V G , λ ik ≥ min (λ ij , λ jk ).
Лемму можно использовать снова и снова, чтобы показать, что выход T удовлетворяет свойствам дерева Гомори – Ху.
Пример
Ниже приводится моделирование алгоритма Гомори – Ху, где
- зеленые круги являются вершинами Т .
- красные и синие кружки - вершины в G '.
- серые вершины - это выбранные s и t .
- красный и синий цвета представляют собой разрез s - t .
- пунктирные края - это отрезки s - t .
- A - это набор вершин, обведенных красным, а B - это набор вершин, обведенных синим .
G ' | Т | |
---|---|---|
| ||
1. | ||
| ||
2. | ||
| ||
3. | ||
| ||
4. | ||
| ||
5. | ||
| ||
6. |
| |
|
Реализации: последовательные и параллельные.
Алгоритм Гусфилда можно использовать для поиска дерева Гомори – Ху без сжатия вершин при той же временной сложности, что упрощает реализацию построения дерева Гомори – Ху. [2]
Эндрю В. Голдберг и К. Циутсиуликлис реализовали алгоритм Гомори-Ху и алгоритм Гусфилда, а также провели экспериментальную оценку и сравнение. [3]
Cohen et al. сообщить о результатах двух параллельных реализаций алгоритма Гасфилда с использованием OpenMP и MPI соответственно. [4]
Связанные понятия
В планарных графах дерево Гомори – Ху двойственно базису цикла минимального веса в том смысле, что разрезы дерева Гомори – Ху двойственны набору циклов в двойственном графе, которые образуют базис цикла минимального веса. [5]
Смотрите также
Рекомендации
- ^ Гоморы, RE ; Ху, TC (1961). «Многотерминальные сетевые потоки». Журнал Общества промышленной и прикладной математики . 9 (4): 551–570. DOI : 10.1137 / 0109047 .
- ^ Гасфилд, Дэн (1990). «Очень простые методы анализа потоков в сети для всех пар». SIAM J. Comput . 19 (1): 143–155. DOI : 10.1137 / 0219009 .
- ^ Гольдберг, А.В.; Циутсиуликлис, К. (2001). «Алгоритмы вырезания дерева: экспериментальное исследование». Журнал алгоритмов . 38 (1): 51–83. DOI : 10.1006 / jagm.2000.1136 .
- ^ Cohen, J .; Л.А. Родригес; Ф. Сильва; Р. Кармо; А. Гуэдес; EP Дуарте младший (2011). "Параллельные реализации алгоритма дерева разрезов Гасфилда". Конспект лекций по информатике (LNCS) . 7016. Springer. 7016 (11-я Международная конференция «Алгоритмы и архитектуры для параллельной обработки» (ICA3PP)): 258–269. DOI : 10.1007 / 978-3-642-24650-0_22 . ISBN 978-3-642-24649-4. ISSN 0302-9743 .
- ^ Hartvigsen, D .; Мардон, Р. (1994). «Задача минимального разреза всех пар и проблема базиса минимального цикла на плоских графах». SIAM J. Дискретная математика . 7 (3): 403–418. DOI : 10,1137 / S0895480190177042 ..
- Б. Х. Корте, Йенс Выген (2008). «8.6 Деревья Гоморы – Ху». Комбинаторная оптимизация: теория и алгоритмы (Алгоритмы и комбинаторика, 21) . Springer Berlin Heidelberg. стр. 180 -186. ISBN 978-3-540-71844-4.