Algoritmo de Stoer-Wagner

Un corte mínimo de un gráfico ponderado que tiene un peso de corte mínimo 4 ^[1]

En teoría de grafos , el algoritmo de Stoer-Wagner es un algoritmo recursivo para resolver el problema de corte mínimo en grafos ponderados no dirigidos con pesos no negativos. Fue propuesto por Mechthild Stoer y Frank Wagner en 1995. La idea esencial de este algoritmo es encoger el gráfico fusionando los vértices más intensivos, hasta que el gráfico solo contenga dos conjuntos de vértices combinados. ^[2] En cada fase, el algoritmo encuentra el mínimo - corte por dos vértices y elegido en su voluntad. Luego, el algoritmo encoge el borde entre y para buscar no -${\displaystyle s}$${\displaystyle t}$${\displaystyle s}$${\displaystyle t}$${\displaystyle s}$${\displaystyle t}$${\displaystyle s}$${\displaystyle t}$cortes. El corte mínimo encontrado en todas las fases será el corte mínimo ponderado del gráfico.

Un corte es una partición de los vértices de un gráfico en dos subconjuntos no vacíos e inconexos. Un corte mínimo es un corte para el cual el tamaño o el peso del corte no es mayor que el tamaño de cualquier otro corte. Para un gráfico no ponderado, el corte mínimo sería simplemente el corte con la menor cantidad de bordes. Para un gráfico ponderado, la suma del peso de todos los bordes en el corte determina si es un corte mínimo. En la práctica, el problema de corte mínimo siempre se discute con el problema de flujo máximo , para explorar la capacidad máxima de una red , ya que el corte mínimo es un cuello de botella en un gráfico o red.

Algoritmo de corte mínimo de Stoer-Wagner

Sea un gráfico no dirigido ponderado. Supongamos eso . El corte se llama - corte si exactamente uno de o está en . El corte mínima de que es también un - corte se denomina - min-corte de . ^[3]${\displaystyle G=(V,E,w)}$${\displaystyle s,t\in V}$${\displaystyle s}$${\displaystyle t}$${\displaystyle s}$${\displaystyle t}$${\displaystyle S}$${\displaystyle G}$${\displaystyle s}$${\displaystyle t}$${\displaystyle s}$${\displaystyle t}$${\displaystyle G}$

Este algoritmo comienza encontrando un y un en , y un st min-cut de . Para cualquier par , hay dos situaciones posibles: o es un min-cut global de , o y pertenecen al mismo lado del min-cut global de . Por lo tanto, el min-corte global se puede encontrar verificando el gráfico , que es el gráfico después de la fusión de los vértices y . Durante la fusión, si y están conectados por un borde, este borde desaparece. Si s y t tienen aristas hacia algún vértice v, entonces el peso de la arista desde el nuevo vértice st hasta v es . ^[3] El algoritmo se describe como: ^[2]${\displaystyle s}$${\displaystyle t}$${\displaystyle V}$${\displaystyle (S,T)}$${\displaystyle G}$${\displaystyle \left\{s,t\right\}}$${\displaystyle (S,T)}$${\displaystyle G}$${\displaystyle s}$${\displaystyle t}$${\displaystyle G}$${\displaystyle G/\left\{s,t\right\}}$${\displaystyle s}$${\displaystyle t}$${\displaystyle s}$${\displaystyle t}$${\displaystyle w(s,v)+w(t,v)}$

MinimumCutPhase mientras se agrega al extremo del vértice más estrechamente conectado ${\displaystyle (G,w,a)}$ ${\displaystyle A\gets \left\{a\right\}}$  ${\displaystyle \ A\neq V}$${\displaystyle A}$ almacenar el corte en el que el último vértice restante está solo (el "corte de la fase") encoge al fusionar los dos vértices (s, t) agregados al final (el valor de "corte de fase" es el valor de mínimo s, t corte).${\displaystyle G}$Mínimo Corte mientras Mínimo Corte Fase si el corte de fase es más ligero que el corte mínimo actual, entonces guarde el corte de fase como el corte mínimo actual${\displaystyle (G,w,a)}$  ${\displaystyle |V|>1}$ ${\displaystyle (G,w,a)}$ 

El algoritmo funciona en fases. En la fase de corte mínimo, el subconjunto de los vértices de los gráficos crece comenzando con un vértice único arbitrario hasta que es igual a . En cada paso, se agrega al conjunto el vértice que está fuera de , pero con el que está más estrechamente conectado . Este procedimiento se puede mostrar formalmente como: ^[2] agregar vértice tal que , donde es la suma de los pesos de todas las aristas entre y . Entonces, en una sola fase, se determina un par de vértices y , y un corte mínimo . ^[4]${\displaystyle A}$${\displaystyle A}$${\displaystyle V}$${\displaystyle A}$${\displaystyle A}$${\displaystyle A}$${\displaystyle z\notin A}$${\displaystyle w(A,z)=\max\{w(A,y)\mid y\notin A\}}$${\displaystyle w(A,y)}$${\displaystyle A}$${\displaystyle y}$${\displaystyle s}$${\displaystyle t}$${\displaystyle s{\text{-}}t}$${\displaystyle C}$Después de una fase de la fase de corte mínimo, los dos vértices se fusionan como un nuevo vértice, y los bordes de los dos vértices al vértice restante se reemplazan por un borde ponderado por la suma de los pesos de los dos bordes anteriores. Se eliminan los bordes que unen los nodos fusionados. Si hay un corte mínimo de separación y , es un corte mínimo de . Si no, entonces el corte mínimo de debe tener y en un mismo lado. Por lo tanto, el algoritmo los fusionaría como un solo nodo. Además, el corte mínimo registraría y actualizaría el corte mínimo global después de cada fase de corte mínimo. Después de las fases, se puede determinar el corte mínimo . ^[4]${\displaystyle G}$${\displaystyle s}$${\displaystyle t}$${\displaystyle C}$${\displaystyle G}$${\displaystyle G}$${\displaystyle s}$${\displaystyle t}$${\displaystyle n-1}$

Ejemplo

Esta sección se refiere a las Figs. 1–6 en el papel original ^[2]

El gráfico del paso 1 muestra el gráfico original y selecciona aleatoriamente el nodo 2 como el nodo inicial de este algoritmo. En la fase de corte mínima, el conjunto solo tiene el nodo 2, el borde más pesado es el borde (2,3), por lo que el nodo 3 se agrega al conjunto . A continuación, el conjunto contiene el nodo 2 y el nodo 3, el borde más pesado es (3,4), por lo que el nodo 4 se agrega al conjunto . Siguiendo este procedimiento, los dos últimos nodos son el nodo 5 y el nodo 1, que están y en esta fase. Al fusionarlos, el nuevo gráfico es como se muestra en el paso 2. En esta fase, el peso de corte es 5, que es la suma de los bordes (1,2) y (1,5). En este momento, se completa el primer ciclo de MinimumCut.${\displaystyle G}$${\displaystyle A}$${\displaystyle A}$${\displaystyle A}$${\displaystyle A}$${\displaystyle s}$${\displaystyle t}$

En el paso 2, comenzando desde el nodo 2, el borde más pesado es (2,15), por lo que el nodo 15 se pone en conjunto . Los siguientes bordes más pesados ​​son (2,3) o (15,6), elegimos (15,6), por lo que el nodo 6 se agrega al conjunto. Luego comparamos el borde (2,3) y (6,7) y elegimos el nodo 3 para ponerlo en conjunto . Los dos últimos nodos son el nodo 7 y el nodo 8. Por lo tanto, combine el borde (7,8). El corte mínimo es 5, por lo que el mínimo es 5.${\displaystyle A}$${\displaystyle A}$

Los siguientes pasos repiten las mismas operaciones en el gráfico combinado, hasta que solo hay un borde en el gráfico, como se muestra en el paso 7. El corte mínimo global tiene borde (2,3) y borde (6,7), que se detecta en el paso 5.

Prueba de corrección

Para probar la exactitud de este algoritmo, necesitamos demostrar que el corte dado por MinimaCutPhase es de hecho un corte mínimo del gráfico, donde syt son los dos vértices agregados por última vez en la fase. Por tanto, a continuación se muestra un lema:${\displaystyle s{\text{-}}t}$

Lema 1 : MinimumCutPhase devuelve un -cut mínimo de .${\displaystyle s{\text{-}}t}$${\displaystyle G}$

Sea un corte arbitrario , y sea ​​el corte dado por la fase. Debemos demostrar eso . Observe que una sola ejecución de MinimumCutPhase nos da un orden de todos los vértices en el gráfico (donde es el primero y y son los dos vértices agregados al final de la fase). Decimos que el vértice está activo si y el vértice agregado justo antes están en lados opuestos del corte. Demostramos el lema por inducción sobre el conjunto de vértices activos. Definimos como el conjunto de vértices añadidos antes , y como el conjunto de aristas hacia adentro con ambos extremos hacia adentro , es decir, es el corte inducido por . Demostramos, para cada vértice activo${\displaystyle C=(X,{\overline {X}})}$${\displaystyle s{\text{-}}t}$${\displaystyle CP}$${\displaystyle W(C)\geq W(CP)}$${\displaystyle a}$${\displaystyle s}$${\displaystyle t}$${\displaystyle v}$${\displaystyle v}$${\displaystyle v}$${\displaystyle A_{v}}$${\displaystyle A}$${\displaystyle v}$${\displaystyle C_{v}}$${\displaystyle C}$${\displaystyle A_{v}\cup \{v\}}$${\displaystyle C_{v}\subseteq C}$${\displaystyle A_{v}\cup \{v\}}$${\displaystyle v}$,

${\displaystyle w(A_{v},v)\leq w(C_{v})}$

Sea el primer vértice activo. Por la definición de estas dos cantidades, y son equivalentes. son simplemente todos los vértices añadidos antes , y los bordes entre estos vértices y son los bordes que cruzan el corte . Por lo tanto, como se muestra arriba, para vértices activos y , con agregado a antes :${\displaystyle v_{0}}$${\displaystyle w(A_{v_{0}},v_{0})}$${\displaystyle w(C_{v_{0}})}$${\displaystyle A_{v_{0}}}$${\displaystyle A}$${\displaystyle v_{0}}$${\displaystyle v_{0}}$${\displaystyle C}$${\displaystyle v}$${\displaystyle u}$${\displaystyle v}$${\displaystyle A}$${\displaystyle u}$

${\displaystyle w(A_{u},u)=w(A_{v},u)+w(A_{u}-A_{v},u)}$

${\displaystyle w(A_{u},u)\leq w(C_{v})+w(A_{u}-A_{v},u)}$ por inducción, ${\displaystyle w(A_{v},u)\leq w(A_{v},v)\leq w(C_{v})}$

${\displaystyle w(A_{u},u)\leq w(C_{u})}$ya que contribuye a pero no a (y otras aristas tienen pesos no negativos)${\displaystyle w(A_{u}-A_{v},u)}$${\displaystyle w(C_{u})}$${\displaystyle w(C_{v})}$

Por lo tanto, ya que es siempre un vértice activo desde el último corte de la fase se separa de , por definición, para cualquier vértice activo :${\displaystyle t}$${\displaystyle s}$${\displaystyle t}$${\displaystyle t}$

${\displaystyle w(A_{t},t)\leq w(C_{t})=w(C)}$

Por lo tanto, el corte de la fase es como máximo tan pesado como .${\displaystyle C}$

Complejidad del tiempo

El tiempo de ejecución del algoritmo MinimalCut es igual al tiempo de ejecución agregado de las ejecuciones de MinimalCutPhase , que se llama en gráficos con un número decreciente de vértices y aristas.${\displaystyle |V|-1}$

Para la fase de corte mínima , se necesita una sola ejecución como máximo .${\displaystyle O(|E|+|V|\log |V|)}$

Por lo tanto, el tiempo de ejecución total debería ser el producto de la complejidad de dos fases, que es [2]. ^[2]${\displaystyle O(|V||E|+|V|^{2}\log |V|)}$

Para la mejora adicional, la clave es facilitar la selección del siguiente vértice que se agregará al conjunto , el vértice más estrechamente conectado. Durante la ejecución de una fase, todos los vértices que no están en residen en una cola de prioridad basada en un campo clave. La clave de un vértice es la suma de los pesos de los bordes de conexión a la corriente , es decir, . Siempre que se agrega un vértice , tenemos que realizar una actualización de la cola. tiene que ser eliminado de la cola, y la clave de cada vértice que no está en , conectado a tiene que incrementarse por el peso del borde , si existe. Como esto se hace exactamente una vez para cada borde, en general tenemos que realizar ExtractMax y${\displaystyle A}$${\displaystyle A}$${\displaystyle V}$${\displaystyle A}$${\displaystyle w(A,v)}$${\displaystyle v}$${\displaystyle A}$${\displaystyle v}$${\displaystyle w}$${\displaystyle A}$${\displaystyle v}$${\displaystyle vw}$${\displaystyle |V|}$${\displaystyle |E|}$IncreaseKey operaciones. Al usar el montón de Fibonacci podemos realizar una operación ExtractMax en tiempo amortizado y una operación IncreaseKey en tiempo amortizado. Por lo tanto, el tiempo que necesitamos para este paso clave que domina el resto de la fase es . ^[2]${\displaystyle O(\log |V|)}$${\displaystyle O(1)}$${\displaystyle O(|E|+|V|\log |V|)}$

Código de ejemplo ^[5]

// Implementación de matriz de adyacencia del algoritmo de corte mínimo de Stoer-Wagner. // // Tiempo de ejecución: // O (| V | ^ 3) // // ENTRADA: // - gráfico, construido usando AddEdge () // // SALIDA: // - (valor de corte mínimo, nodos a la mitad de corte mínimo)#include  <cmath>#include  <vector>#include  <iostream>usando el  espacio de nombres  std ;typedef  vector < int >  VI ; typedef  vector < VI >  VVI ;const  int  INF  =  1000000000 ;par < int ,  VI >  GetMinCut ( VVI  y pesos )  {  int  N  =  pesos . tamaño ();  VI  usado ( N ),  cut ,  best_cut ;  int  best_weight  =  -1 ; para  ( int  fase  =  N -1 ;  fase  > =  0 ;  fase - )  {  VI  w  =  pesos [ 0 ];  VI  agregado  =  usado ;  int  prev ,  last  =  0 ;  for  ( int  i  =  0 ;  i  <  fase ;  i ++ )  {  prev  =  last ;  último  =  -1;  for  ( int  j  =  1 ;  j  <  N ;  j ++ )  {  if  ( ! added [ j ]  &&  ( last  ==  -1  ||  w [ j ]  >  w [ last ]))  last  =  j ;  }  si  ( i  ==  fase -1 )  {  para  ( int  j  =  0 ; j  <  N ;  j ++ )  pesos [ anterior ] [ j ]  + =  pesos [ último ] [ j ];  para  ( int  j  =  0 ;  j  <  N ;  j ++ )  pesos [ j ] [ prev ]  =  pesos [ prev ] [ j ];  usado [ último ]  =  verdadero ;  cortar .push_back ( último );  // esta parte da una respuesta incorrecta.  // EX) n = 4, 1er paso: prev = 1, last = 2 / 2do paso: prev = 3, last = 4  // si el 2do paso da mincut, el corte es {1,2,3}, {4 } pero este código da una respuesta incorrecta - {1,3}, {2,4}  if  ( best_weight  ==  -1  ||  w [ last ]  <  best_weight )  {  best_cut  =  cut ;  mejor_peso  =  w [ último ];  }  }  else  {  para  ( int  j  =  0 ; j  <  N ;  j ++ )  {  w [ j ]  + =  pesos [ último ] [ j ];  agregado [ último ]  =  verdadero ;  }  }  }  }  return  make_pair ( mejor_peso ,  mejor_corte ); }

^{[ cita requerida ]}

const  int  maxn  =  550 ;  const  int  inf  =  1000000000 ;  int  n ,  r ;  int  borde [ maxn ] [ maxn ],  dist [ maxn ];  bool  vis [ maxn ],  bin [ maxn ];  void  init ()  {  memset ( borde ,  0 ,  tamaño de ( borde ));  memset ( contenedor,  falso ,  tamaño de ( contenedor ));  }  int  contract (  int  & s ,  int  & t  )  // Encuentra s, t {  memset ( dist ,  0 ,  sizeof ( dist ));  memset ( vis ,  false ,  sizeof ( vis ));  int  i ,  j ,  k ,  mincut ,  maxc ;  para  ( yo =  1 ;  i  <=  n ;  i ++ )  {  k  =  -1 ;  maxc  =  -1 ;  para  ( j  =  1 ;  j  <=  n ;  j ++ ) si  ( ! bin [ j ]  &&  ! vis [ j ]  &&  dist [ j ]  >  maxc )  {  k  =  j ;  maxc =  dist [ j ];  }  if  ( k  ==  -1 )  return  mincut ;  s  =  t ;  t  =  k ;  mincut  =  maxc ;  vis [ k ]  =  verdadero ;  para  ( j  =  1 ;  j  <=  n ;  j ++ )  si  ( ! bin [ j ]  &&  ! vis [j ])  dist [ j ]  + =  borde [ k ] [ j ];  }  return  mincut ;  }int  Stoer_Wagner ()  {  int  mincut ,  i ,  j ,  s ,  t ,  ans ;  para  ( mincut  =  inf ,  i  =  1 ;  i  <  n ;  i ++ )  {  ans  =  contract (  s ,  t  );  bin [ t ]  =  verdadero ;  if  ( mincut  >  ans )  mincut =  ans ;  if  ( mincut  ==  0 )  return  0 ;  for  ( j  =  1 ;  j  <=  n ;  j ++ )  if  ( ! bin [ j ])  edge [ s ] [ j ]  =  ( edge [ j ] [ s ]  + =  edge [ j ] [ t ]);  }  return  mincut ;  }

Referencias

1. "Biblioteca de gráficos de impulso: Stoer-Wagner Min-Cut - 1.46.1" . www.boost.org . Consultado el 7 de diciembre de 2015 .
2. "Un algoritmo simple de corte mínimo" .
3. "Notas de la conferencia para el análisis de algoritmos": cortes mínimos globales " (PDF) .
4. "El algoritmo de corte mínimo de Stoer y Wagner" (PDF) .
5. "Cuaderno del equipo ACM de la Universidad de Stanford (2014-15)" . web.stanford.edu . Consultado el 7 de diciembre de 2015 .

enlaces externos

• StoerWagnerMinCut.java : una biblioteca Java que implementa el algoritmo Stoer-Wagner