13.4: El algoritmo de etiquetado de Ford-Fulkerson
- Page ID
- 118252
En esta sección, describimos el clásico algoritmo de etiquetado Ford-Fulkerson para encontrar un flujo máximo en una red. El algoritmo comienza con un orden lineal en el conjunto de vértices que establece una noción de precedencia. Normalmente, el primer vértice en este orden lineal es la fuente mientras que el segundo es el sumidero. Después de eso, los vértices se pueden enumerar en cualquier orden. En este libro, utilizaremos la siguiente convención: los vértices se etiquetarán con mayúsculas del alfabeto inglés y el orden lineal será,\((S,T,A,B,C,D,E,F,G,…)\), al que nos referiremos como el orden pseudo-alfabético. Por supuesto, esta convención sólo tiene sentido para redes con como máximo 26 vértices, pero esta limitación no calmará nuestro estilo. Para problemas del mundo real, nos consolamos en el hecho de que las computadoras pueden lidiar con bastante facilidad con claves enteras de casi cualquier tamaño.
Antes de proporcionar una descripción precisa del algoritmo, tomemos un minuto para considerar una visión general. Al llevar a cabo el algoritmo de etiquetado, los vértices se clasificarán como etiquetados o no etiquetados. Al principio, comenzaremos con solo etiquetar la fuente mientras que todos los demás vértices quedarán sin etiquetar. Por criterios aún por detallar, consideraremos sistemáticamente los vértices no etiquetados y determinaremos cuáles deben etiquetarse. Si alguna vez etiquetamos el fregadero, entonces habremos descubierto un camino de aumento, y el flujo se actualizará adecuadamente. Después de actualizar el flujo, comenzamos de nuevo con solo etiquetar la fuente.
Este proceso se repetirá hasta que (y veremos que esto siempre ocurre) lleguemos a un punto donde el etiquetado se detiene con algunos vértices etiquetados (uno de estos es el origen) y algunos vértices sin etiquetar (uno de estos es el sumidero). Entonces notaremos que la partición\(V=L \cup U\) en vértices etiquetados y no etiquetados (de ahí nuestra elección de\(L\) y\(U\) como nombres) es un corte cuya capacidad es exactamente igual al valor del flujo de corriente. Esto resuelve el debate de antes en el capítulo y dice que la cuestión de flujo máximo/corte mínimo es más como anticadena y partición en cadenas que número de camarilla y número cromático. En particular, el algoritmo de etiquetado proporcionará una prueba del siguiente teorema:
\(G=(V,E)\)Déjese ser una red. Si\(v_0\) es el valor máximo de un flujo y\(c_0\) es la capacidad mínima\(c_0\) de un corte, entonces\(v_0=c_0\).
Ahora estamos listos para describir en detalle el algoritmo de etiquetado de Ford-Fulkerson.
Etiquetado de los vértices
Los vértices serán etiquetados con triples ordenados de símbolos. Cada vez que iniciamos el proceso de etiquetado, comenzamos etiquetando la fuente con el triple\((∗,+,∞)\). Las reglas por las que etiquetamos vértices serán explícitas.
Potencial en un vértice etiquetado
Dejar\(u\) ser un vértice etiquetado. La tercera coordenada de la etiqueta que se le da\(u\) será el número real positivo, aunque puede ser infinito. Llamamos a esta cantidad el potencial sobre\(u\) y la denotamos por\(p(u)\). (El potencial servirá como la cantidad por la que se puede actualizar el flujo.) Obsérvese que el potencial sobre la fuente es infinito.
Primero etiquetado, primero escaneado
El algoritmo de etiquetado implica una exploración de un vértice etiquetado\(u\). A medida que se etiquetan los vértices, determinan otro orden lineal. La fuente siempre será el primer vértice en este orden. Después de eso, el orden en que se etiquetan los vértices cambiará con el tiempo. Pero la regla importante es que escaneamos los vértices en el orden en que se etiquetan, hasta que etiquetemos el sumidero. Si, por ejemplo, el escaneo inicial, siempre realizado desde el origen, da como resultado que las etiquetas se apliquen a los vértices\(D, G\) y (M\), entonces luego escaneamos desde el vértice\(D\). Si ese escaneo da como resultado vértices\(B, F, G\) y\(Q\) ser etiquetados, entonces luego escaneamos desde\(G\), como se etiquetó antes\(B\), aunque\(B\) precede\(G\) en el orden pseudo-alfabético. Este aspecto del algoritmo da como resultado una búsqueda en primer plano de los vértices buscando formas de etiquetar vértices previamente no etiquetados.
Nunca vuelva a etiquetar un vértice
Una vez que se etiqueta un vértice, no cambiamos su etiqueta. Estamos contentos de etiquetar los vértices previamente sin etiquetar, hasta el momento en que etiquetamos el sumidero. Entonces, después de actualizar el flujo y aumentar el valor, todas las etiquetas, excepto por supuesto la etiqueta especial en la fuente, se descartan y comenzamos de nuevo.
Etiquetado de vértices mediante bordes delanteros
Supongamos que estamos escaneando desde un vértice etiquetado\(u\) con potencial\(p(u)>0\). A partir de\(u\), consideramos a los vecinos no etiquetados de\(u\) en orden pseudo-alfabético. Ahora supongamos que estamos mirando a un vecino\(v\) de\(u\) con el borde\((u,v)\) perteneciente a la red. Esto significa que el borde se dirige de\(u\) a\(v\). Si no\(e=(u,v)\) está lleno, entonces etiquetamos el vértice\(v\) con el triple\((u,+,p(v))\) donde\(p(v)=min\{p(u),c(e)−ϕ(e)\}\). Utilizamos esta definición ya que el flujo no se puede aumentar en más que el potencial anterior o la capacidad sobrante en\(e\). Tenga en cuenta que el potencial\(p(v)\) es positivo ya que a es el mínimo de dos números positivos.
Etiquetado de vértices mediante bordes hacia atrás
Ahora supongamos que estamos mirando a un vecino\(v\) de\(u\) con el borde\((v,u)\) perteneciente a la red. Esto significa que el borde se dirige de\(v\) a\(u\). Si\(e=(v,u)\) se usa, entonces etiquetamos el vértice\(v\) con el triple\((u,−,p(v))\) donde\(p(v)=min\{p(u),ϕ(e)\}\). Aquí\(p(v)\) se define de esta manera ya que el flujo encendido\(e\) no se puede disminuir en más de\(ϕ(e)\) o\(p(u)\). Nuevamente, señalar que el potencial\(p(v)\) es positivo ya que\(a\) es el mínimo de dos números positivos
¿Qué sucede cuando se etiqueta el fregadero?
El algoritmo de etiquetado se detiene si alguna vez se etiqueta el sumidero. Tenga en cuenta que siempre estamos haciendo nuestro mejor esfuerzo para etiquetar el fregadero, ya que en cada escaneo el fregadero es el primer vértice a considerar. Ahora supongamos que el fregadero está etiquetado con el triple\((u,+,a)\). Tenga en cuenta que la segunda coordenada en la etiqueta debe ser\(+\) ya que todos los bordes incidentes con el fregadero están orientados hacia el fregadero.
Afirmamos que podemos encontrar un camino de aumento\(P\) que se traduce en un aumento del flujo con\(δ=a\), el potencial en el fregadero. Para ver esto, simplemente retrocedemos. El fregadero\(T\) obtuvo su etiqueta de\(u=u_1, u_1\) obtuvo su etiqueta de\(u_2\), y así sucesivamente. Finalmente, descubrimos un vértice\(u_m\) que obtuvo su etiqueta de la fuente. El camino de aumento es entonces
\(P=(S,u_m,u_{m−1},…,u_1,T)\).
El valor de\(δ\) para este camino es el potencial\(p(T)\) en el fregadero ya que hemos asegurado cuidadosamente que
\(p(u_m) \geq p(u_{m-1}) \geq \cdot \cdot \cdot \geq p(u_1) \geq p(T)\).
¿Y si el Lavabo no está Etiquetado?
Por otro lado, supongamos que hemos escaneado desde cada vértice etiquetado y aún quedan vértices sin etiquetar, uno de los cuales es el sumidero. Ahora reclamamos la victoria. Para ver que hemos ganado, simplemente observamos que si\(L\) es el conjunto de vértices etiquetados, y\(U\) es el conjunto de vértices sin etiquetar, entonces cada borde\(e=(x,y)\) con\(x \in L\) y\(y \in U\) está lleno, es decir,\(ϕ(e)=c(e)\) . Si este no fuera el caso, entonces\(y\) calificaría para una etiqueta con\(x\) como la primera coordenada. Además, tenga en cuenta que\(ϕ(y,x)=0\) para cada borde\(e\) con\(x \in L\) y\(y \in U\). Independientemente, vemos que la capacidad del corte\(V=L \cup U\) es exactamente igual al valor del flujo de corriente, por lo que tenemos tanto un flujo máximo como un corte mínimo proporcionando un certificado de optimalidad.