Árbol de Gomory-Hu

Árbol ponderado que representa los cortes st de un gráfico

En optimización combinatoria , el árbol de Gomory-Hu ^[1] de un grafo no dirigido con capacidades es un árbol ponderado que representa los cortes s - t mínimos para todos los pares s - t en el grafo. El árbol de Gomory-Hu se puede construir en | V | − 1 cálculos de flujo máximo . Recibe su nombre en honor a Ralph E. Gomory y TC Hu .

Definición

Sea un grafo no dirigido con la capacidad de la arista respectivamente. ${\displaystyle G=(V_{G},E_{G},c)}$ ${\displaystyle c(u,v)}$ ${\displaystyle (u,v)}$

Denota la capacidad mínima de un corte s - t por para cada . ${\displaystyle \lambda _{st}}$ ${\displaystyle s,t\in V_{G}}$

Sea un árbol, y denotemos el conjunto de aristas en una ruta s - t por para cada . ${\displaystyle T=(V_{G},E_{T})}$ ${\displaystyle P_{st}}$ ${\displaystyle s,t\in V_{G}}$

Entonces se dice que T es un árbol de Gomory-Hu de G , si para cada ${\displaystyle s,t\in V_{G}}$

${\displaystyle \lambda _{st}=\min _{e\in P_{st}}c(S_{e},T_{e}),}$

dónde

1. ${\displaystyle S_{e},T_{e}\subseteq V_{G}}$son los dos componentes conectados de , y por lo tanto forman un corte s - t en G . ${\displaystyle T\setminus \{e\}}$ ${\displaystyle (S_{e},T_{e})}$
2. ${\displaystyle c(S_{e},T_{e})}$es la capacidad del corte en G. ${\displaystyle (S_{e},T_{e})}$

Algoritmo

Algoritmo de Gomory-Hu

Entrada : Un gráfico no dirigido ponderado ${\displaystyle G=((V_{G},E_{G}),c)}$

Resultado : Un árbol de Gomory-Hu ${\displaystyle T=(V_{T},E_{T}).}$

1. Colocar ${\displaystyle V_{T}=\{V_{G}\},\ E_{T}=\emptyset .}$
2. Elija alguno con | X | ≥ 2 si existe tal X. De lo contrario, vaya al paso 6. ${\displaystyle X\in V_{T}}$
3. Para cada componente conectado, dejemos ${\displaystyle C=(V_{C},E_{C})\in T\setminus X,}$ ${\textstyle S_{C}=\bigcup _{v_{T}\in V_{C}}v_{T}.}$

   Dejar ${\displaystyle S=\{S_{C}\mid C{\text{ is a connected component in }}T\setminus X\}.}$

   Contrae los componentes para formar donde: ${\displaystyle G'=((V_{G'},E_{G'}),c'),}$ $${\displaystyle {\begin{aligned}V_{G'}&=X\cup S\\[2pt]E_{G'}&=E_{G}|_{X\times X}\cup \{(u,S_{C})\in X\times S\mid (u,v)\in E_{G}{\text{ for some }}v\in S_{C}\}\\[2pt]&\qquad \qquad \quad \!\cup \{(S_{C1},S_{C2})\in S\times S\mid (u,v)\in E_{G}{\text{ for some }}u\in S_{C1}{\text{ and }}v\in S_{C2}\}\end{aligned}}}$$

   ${\displaystyle c':V_{G'}\times V_{G'}\to R^{+}}$es la función de capacidad, definida como: $${\displaystyle {\begin{aligned}&{\text{if }}\ (u,S_{C})\in E_{G}|_{X\times S}:&&c'(u,S_{C})=\!\!\!\sum _{\begin{smallmatrix}v\in S_{C}:\\(u,v)\in E_{G}\end{smallmatrix}}\!\!\!c(u,v)\\[4pt]&{\text{if }}\ (S_{C1},S_{C2})\in E_{G}|_{S\times S}:&&c'(S_{C1},S_{C2})=\!\!\!\!\!\!\!\sum _{\begin{smallmatrix}(u,v)\in E_{G}:\\u\in S_{C1}\,\land \,v\in S_{C2}\end{smallmatrix}}\!\!\!\!\!c(u,v)\\[4pt]&{\text{otherwise}}:&&c'(u,v)=c(u,v)\end{aligned}}}$$

4. Elija dos vértices s , t ∈ X y encuentre un corte s - t mínimo ( A′ , B′ ) en G' .

   Colocar ${\displaystyle A={\Biggl (}\bigcup _{S_{C}\in A'\cap S}\!\!\!S_{C}\!{\Biggr )}\cup (A'\cap X),\ }$ ${\displaystyle B={\Biggl (}\bigcup _{S_{C}\in B'\cap S}\!\!\!S_{C}\!{\Biggr )}\cup (B'\cap X).}$

5. Colocar ${\displaystyle V_{T}=(V_{T}\setminus X)\cup \{A\cap X,B\cap X\}.}$

   Para cada uno haz lo siguiente: ${\displaystyle e=(X,Y)\in E_{T}}$

   1. Establecer si se establece de otra manera ${\displaystyle e'=(A\cap X,Y)}$ ${\displaystyle Y\subset A,}$ ${\displaystyle e'=(B\cap X,Y).}$
   2. Colocar ${\displaystyle E_{T}=(E_{T}\setminus \{e\})\cup \{e'\}.}$
   3. Colocar ${\displaystyle w(e')=w(e).}$

   Colocar ${\displaystyle E_{T}=E_{T}\cup \{(A\cap X,\ B\cap X)\}.}$

   Colocar ${\displaystyle w((A\cap X,B\cap X))=c'(A',B').}$

   Vaya al paso 2.

6. Reemplace cada uno por v y cada uno por ( u , v ) . Salida T . ${\displaystyle \{v\}\in V_{T}}$ ${\displaystyle (\{u\},\{v\})\in E_{T}}$

Análisis

Usando la propiedad submodular de la función de capacidad c , se tiene Entonces se puede demostrar que el corte mínimo s - t en G' es también un corte mínimo s - t en G para cualquier s , t ∈ X . $${\displaystyle c(X)+c(Y)\geq c(X\cap Y)+c(X\cup Y).}$$

Para demostrar que para todos los p ∈ P , q ∈ Q a lo largo del algoritmo, se utiliza el siguiente lema, ${\displaystyle (P,Q)\in E_{T},}$ ${\displaystyle w(P,Q)=\lambda _{pq}}$

Para cualquier i, j, k en V _G , ${\displaystyle \lambda _{ik}\geq \min(\lambda _{ij},\lambda _{jk}).}$

El lema se puede utilizar nuevamente repetidamente para demostrar 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

1. Los círculos verdes son vértices de T.
2. Los círculos rojos y azules son los vértices en G '.
3. Los vértices grises son los s y t elegidos .
4. Los colores rojo y azul representan el corte s - t .
5. Los bordes discontinuos son el corte s - t .
6. A es el conjunto de vértices rodeados en rojo y B es el conjunto de vértices rodeados en azul .

Implementaciones: secuenciales y paralelas

El algoritmo de Gusfield se puede utilizar para encontrar un árbol de Gomory-Hu sin ninguna contracción de vértices 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 Gomory-Hu y el algoritmo Gusfield, y realizaron una evaluación y comparación experimental. ^[3]

Cohen et al. informan los resultados de dos implementaciones paralelas del algoritmo de Gusfield utilizando OpenMP y MPI, respectivamente. ^[4]

Conceptos relacionados

En los grafos planares , el árbol de Gomory-Hu es dual con respecto a la base del ciclo de peso mínimo , en el sentido de que los cortes del árbol de Gomory-Hu son duales con respecto a una colección de ciclos en el grafo dual que forman una base del ciclo de peso mínimo. ^[5]

Véase también

• Corte (teoría de grafos)
• Teorema de corte mínimo de flujo máximo
• Problema de flujo máximo

Referencias

1. 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.
2. Gusfield, Dan (1990). "Métodos muy simples para el análisis del flujo de redes de todos los pares". SIAM J. Comput . 19 (1): 143–155. doi :10.1137/0219009.
3. Goldberg, AV; Tsioutsiouliklis, K. (2001). "Algoritmos de árboles de corte: un estudio experimental". Revista de algoritmos . 38 (1): 51–83. doi :10.1006/jagm.2000.1136.
4. Cohen, Jaime; Rodrigues, Luiz A.; Silva, Fabiano; Carmo, Renato; Guedes, André Luiz Pires; Duarte, Jr., Elias P. (2011). "Implementaciones paralelas del algoritmo de árbol de corte de Gusfield". En Xiang, Yang; Cuzzocrea, Alfredo; Hobbs, Michael; Zhou, Wanlei (eds.). Algoritmos y arquitecturas para procesamiento paralelo – 11.ª conferencia internacional, ICA3PP, Melbourne, Australia, 24-26 de octubre de 2011, Actas, Parte I. Lecture Notes in Computer Science. Vol. 7016. Springer. págs. 258-269. doi :10.1007/978-3-642-24650-0_22. ISBN . 978-3-642-24649-4.{{cite conference}}: CS1 maint: multiple names: authors list (link)
5. Hartvigsen, D.; Mardon, R. (1994). "El problema del corte mínimo de todos los pares y el problema de la base del ciclo mínimo en grafos planares". SIAM J. Discrete Math . 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 Berlin Heidelberg. págs. 180–186. ISBN 978-3-540-71844-4.