Árbol de Gomory-Hu

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

En optimización combinatoria , el árbol 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 Gomory-Hu se puede construir en | V | − 1 cálculos de caudal máximo . Lleva el nombre de Ralph E. Gomory y TC Hu .

Definición

Sea un gráfico no dirigido siendo la capacidad del borde respectivamente. ${\displaystyle G=(V_{G},E_{G},c)}$ ${\displaystyle c(u,v)}$ ${\displaystyle (u,v)}$

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

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

Entonces se dice que T es un árbol 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 ponderado no dirigido ${\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. Elige algunos con | X | ≥ 2 si tal X existe. De lo contrario, vaya al paso 6. ${\displaystyle X\in V_{T}}$
3. Para cada componente conectado, deje ${\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\}.}$

   Contrate 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 mínimo s - t ( 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 hacer: ${\displaystyle e=(X,Y)\in E_{T}}$

   1. Establecer si se establece lo contrario ${\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

$${\displaystyle c(X)+c(Y)\geq c(X\cap Y)+c(X\cup Y).}$$

s - t's - t en Gs , t ∈ X.

Para demostrar que para todo y para algún 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 mostrar que la salida T satisface las propiedades de un árbol 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. El color rojo y azul representa el corte s - t .
5. Los bordes discontinuos son el conjunto de corte s - t .
6. A es el conjunto de vértices encerrados en rojo y B es el conjunto de vértices encerrados en azul .

Implementaciones: secuencial y paralela

El algoritmo de Gusfield se puede utilizar para encontrar un árbol 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 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 y cols. informar los resultados sobre dos implementaciones paralelas del algoritmo de Gusfield utilizando OpenMP y MPI, respectivamente. ^[4]

Conceptos relacionados

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

Ver también

• Cortar (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 de flujo de red de todos los pares". SIAM J. Computación . 19 (1): 143-155. doi :10.1137/0219009.
3. Goldberg, AV; Tsioutsiouliklis, K. (2001). "Algoritmos de árbol cortado: 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., Elías 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 al 26 de octubre de 2011, Actas, Parte I. Apuntes de conferencias sobre informática. vol. 7016. Saltador. págs. 258–269. doi :10.1007/978-3-642-24650-0_22.{{cite conference}}: CS1 maint: multiple names: authors list (link)
5. Hartvigsen, D.; Mardón, R. (1994). "El problema de corte mínimo de todos los pares y el problema de base de ciclo mínimo en gráficos planos". 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. págs. 180–186. ISBN 978-3-540-71844-4.