En la optimización combinatoria , el árbol de Gomory-Hu [1] de un gráfico no dirigido con capacidades es un árbol ponderado que representa los cortes mínimos s - t para todos los pares s - t en el gráfico. El árbol de Gomory-Hu se puede construir en | V | - 1 cálculo de caudal máximo .
Definición
Sea G = (( V G , E G ), c ) un gráfico no dirigido con c ( u , v ) siendo la capacidad de la arista ( u , v ) respectivamente.
- Denotar la capacidad mínima de un st corte por λ st para cada uno s , t ∈ V G .
- Deje que T = ( V G , E T ) ser un árbol, denotan el conjunto de aristas en un st camino por P st para cada uno s , t ∈ V G .
Entonces se dice que T es un árbol de Gomory-Hu de G , si para cada s , t ∈ V G
- λ st = min e∈P st c ( S e , T e ),
dónde
- S e , T e ⊆ V G son los dos componentes conectados de T ∖ { e }, y por lo tanto ( S e , T e ) forman una s - t corte en G .
- c ( S e , T e ) es la capacidad del corte en G .
Algoritmo
Algoritmo de Gomory-Hu
- Entrada : Un gráfico no dirigido ponderado G = (( V G , E G ), c )
- Resultado : Un árbol de Gomory – Hu T = ( V T , E T ).
- 1. Establezca V T = { V G } y E T = ∅.
- 2. Elija algo de X ∈ V T con | X | ≥ 2 si tal X existe. De lo contrario, vaya al paso 6.
- 3. Para cada componente conectado C = ( V C , E C ) en T ∖ X . Let S C = ∪ v T ∈V C v T . Sea S = { S C | C es un componente conectado en T ∖ X }.
- Contrae los componentes para formar G '= (( V G' , E G ' ), c '), donde
- V G' = X ∪ S .
- E G ' = E G | X × X ∪ {( u , S C ) ∈ X × S | ( u , v ) ∈ E G para algunos v ∈ S C } ∪ {( S C1 , S C2 ) ∈ S × S | ( u , v ) ∈ E G para algunos u∈ S C1 y v ∈ S C2 }.
- c ': V G' × V G ' → R + es la función de capacidad definida como,
- si ( u , S C ) ∈ E G | X × S , c '( u , S C ) = Σ v∈S C : (u, v) ∈E G c ( u , v ),
- si ( 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 ) de lo contrario.
- 4. Elija dos vértices s , t ∈ X y encuentre un corte s - t mínimo ( A ', B ') en G '.
- Establezca A = (∪ S C ∈ A '∩ S S C ) ∪ ( A ' ∩ X ) y B = (∪ S C ∈ B '∩ S S C ) ∪ ( B ' ∩ X ).
- 5. Establezca V T = ( V T ∖ X ) ∪ { A ∩ X , B ∩ X }.
- Para cada e = ( X , Y ) ∈ E T hacer
- Si Y ⊂ A , establezca e '= ( A ∩ X , Y ), de lo contrario, establezca e ' = ( B ∩ X , Y ).
- Establezca E T = ( E T ∖ { e }) ∪ { e '} yw ( e ') = w ( e ).
- Establezca E T = E T ∪ {( A ∩ X , B ∩ X )}.
- Establezca w (( A ∩ X , B ∩ X )) = c '( A ', B ').
- Vaya al paso 2.
- 6. Reemplaza cada { v } ∈ V T por v y cada ({ u }, { v }) ∈ E T por ( u , v ). Salida T .
Análisis
Usando la propiedad submodular de la función de capacidad c , uno tiene
- c ( X ) + c ( Y ) ≥ c ( X ∩ Y ) + c ( X ∪ Y ).
Entonces se puede demostrar que el mínimo s - t corte en G 'es también un mínimo s - t corte en G para cualquier s , t ∈ X .
Para mostrar que para todo ( P , Q ) ∈ E T , w ( P , Q ) = λ pq para algunos p ∈ P , q ∈ Q en todo el algoritmo, se hace uso del siguiente Lema,
- Para cualquier i , j , k en V G , λ ik ≥ min (λ ij , λ jk ).
El lema se puede usar nuevamente repetidamente para mostrar que la salida T satisface las propiedades de un árbol de Gomory-Hu.
Ejemplo
La siguiente es una simulación del algoritmo de Gomory-Hu, donde
- verdes círculos son vértices de T .
- los círculos rojos y azules son los vértices en G '.
- los vértices grises son las s y t elegidas .
- la coloración roja y azul representa el corte s - t .
- los bordes punteados son los cortes de s - t .
- A es el conjunto de vértices encerrados en un círculo rojo y B es el conjunto de vértices encerrados en un círculo en azul .
G ' | T | |
---|---|---|
| ||
1. | ||
| ||
2. | ||
| ||
3. | ||
| ||
4. | ||
| ||
5. | ||
| ||
6. |
| |
|
Implementaciones: secuenciales y paralelas
El algoritmo de Gusfield se puede utilizar para encontrar un árbol de Gomory-Hu sin ninguna contracción de vértice en la misma complejidad de tiempo de ejecución, lo que simplifica la implementación de la construcción de un árbol de Gomory-Hu. [2]
Andrew V. Goldberg y K. Tsioutsiouliklis implementaron el algoritmo de Gomory-Hu y el algoritmo de Gusfield, y realizaron una evaluación y comparación experimental. [3]
Cohen y col. reportan resultados sobre dos implementaciones paralelas del algoritmo de Gusfield usando OpenMP y MPI, respectivamente. [4]
Conceptos relacionados
En los gráficos planos , el árbol de Gomory-Hu es dual con la base del ciclo de peso mínimo , en el sentido de que los cortes del árbol de Gomory-Hu son duales con una colección de ciclos en el gráfico dual que forman una base de ciclo de peso mínimo. [5]
Ver también
Referencias
- ^ Gomory, RE ; Hu, TC (1961). "Flujos de red multiterminal". Revista de la Sociedad de Matemáticas Industriales y Aplicadas . 9 (4): 551–570. doi : 10.1137 / 0109047 .
- ^ Gusfield, Dan (1990). "Métodos muy simples para todos los pares de análisis de flujo de red". SIAM J. Comput . 19 (1): 143-155. doi : 10.1137 / 0219009 .
- ^ Goldberg, AV; Tsioutsiouliklis, K. (2001). "Algoritmos de árboles cortados: un estudio experimental". Revista de algoritmos . 38 (1): 51–83. doi : 10.1006 / jagm.2000.1136 .
- ^ Cohen, J .; LA Rodrigues; F. Silva; R. Carmo; A. Guedes; EP Duarte Jr. (2011). "Implementaciones paralelas del algoritmo de árbol cortado de Gusfield". Lecture Notes in Computer Science (LNCS) . 7016. Springer. 7016 (11ª Conferencia Internacional sobre algoritmos y arquitecturas para procesamiento en paralelo (ICA3PP)): 258–269. doi : 10.1007 / 978-3-642-24650-0_22 . ISBN 978-3-642-24649-4. ISSN 0302-9743 .
- ^ Hartvigsen, D .; Mardon, R. (1994). "El problema de corte mínimo de todos los pares y el problema de base de ciclo mínimo en gráficos planares". SIAM J. Matemáticas discretas . 7 (3): 403–418. doi : 10.1137 / S0895480190177042 ..
- BH Korte, Jens Vygen (2008). "8.6 Árboles de Gomory-Hu". Optimización combinatoria: teoría y algoritmos (algoritmos y combinatoria, 21) . Springer Berlín Heidelberg. pp. 180 -186. ISBN 978-3-540-71844-4.