13.3: Aumentando caminos
- Page ID
- 118242
En esta sección, desarrollamos el algoritmo de etiquetado clásico de Ford y Fulkerson que comienza con cualquier flujo en una red y procede a modificar el flujo, siempre aumentando el valor del flujo, hasta llegar a un paso en el que no son posibles más mejoras. El algoritmo también ayudará a resolver el debate que Alice, Bob, Carlos y Yolanda estaban teniendo en la sección anterior.
Nuestra presentación del algoritmo de etiquetado hace uso de una terminología natural y bastante descriptiva. Supongamos que tenemos una red\(\textbf{G}=(V,E)\) con un flujo\(ϕ\) de valor\(v\). Llamamos flujo\(ϕ\) de corriente y buscamos formas de aumentar\(ϕ\) haciendo un número relativamente pequeño de cambios. Se dice que\(ϕ(x,y)>0\) se usa una arista\((x,y)\) con, y cuando\(ϕ(x,y)=c(x,y)>0\), decimos que la arista está llena. Cuando\(ϕ(x,y)<c(x,y)\), decimos que el borde\((x,y)\) tiene capacidad sobrante, y cuando\(0=ϕ(x,y)<c(x,y)\), decimos que el borde\((x,y)\) está vacío. Tenga en cuenta que simplemente ignoramos los bordes con capacidad cero.
La herramienta clave para modificar un flujo de red es un tipo especial de ruta, y estas rutas no son necesariamente rutas dirigidas. Una ruta de aumento es una secuencia\(P=(x_0,x_1,…,x_m)\) de vértices distintos en la red de tal manera que\(x_0=S, x_m=T\), y para cada uno\(i=1,2,…,m\),
- \((x_{i−1},x_i)\)tiene capacidad sobrante o
- \((x_i,x_{i−1})\)se utiliza.
Cuando se mantiene la condición (Elemento a), es costumbre referirse al borde\((x_{i−1},x_i)\) como un borde delantero de la ruta de aumento\(P\). De manera similar, si se mantiene la condición (Elemento b), entonces el borde (no dirigido)\((x_{i−1},x_i)\) se denomina borde hacia atrás ya que el camino se mueve de\(x_{i−1}\) a\(x_i\), que es opuesto a la dirección del borde.
Volvamos a ver la red y el flujo en la Figura 13.2. La secuencia de vértices\((S,F,A,T)\) cumple con los criterios para ser una ruta de aumento, y cada borde en ella es un borde delantero. Observe que aumentar el flujo en cada uno de\((S,F), (F,A)\), y\((A,T)\) por cualquier cantidad positiva\(δ≤12\) da como resultado aumentar el valor del flujo y preserva las leyes de conservación.
Si nuestro primer ejemplo te saltó como un camino de aumento, probablemente sea menos claro a simple vista que también\((S,E,D,C,B,A,T)\) es un camino de aumento. Todos los bordes son bordes delanteros excepto por\((C,B)\), ya\((B,C)\) que en realidad es un borde dirigido en la red. No te preocupes si no está claro cómo se puede utilizar este camino para aumentar el valor del flujo en la red, ya que ese es nuestro siguiente tema.
Ignorando, por el momento, el tema de encontrar caminos aumentadores, veamos cómo se pueden utilizar para modificar el flujo de corriente de una manera que aumente su valor por algunos\(δ>0\). He aquí cómo para un camino de aumento\(P=(x_0,x_1,…,x_m)\). Primero, deja\(δ_1\) ser el número positivo definido por:
\(δ_1=min\{c(x_{i−1},x_i)−ϕ(x_{i−1},x_i):(x_{i−1},x_i)\)un borde delantero de\(P\).}
La cantidad no\(c(x_{i−1},x_i)−ϕ(x_{i−1},x_i)\) es más que la capacidad sobrante en el borde\((x_{i−1},x_i)\), y por lo tanto\(δ_1\) es la mayor cantidad por la que todos los bordes delanteros de\(P\). Tenga en cuenta que los bordes\((x_0,x_1)\) y\((x_{m−1},x_m)\) son siempre bordes delanteros, por lo que la cantidad positiva\(δ_1\) se define para cada camino de aumento.
Cuando el camino de aumento no\(P\) tiene bordes hacia atrás, establecemos\(δ=δ_1\). Pero cuando\(P\) tiene uno o más bordes hacia atrás, hacemos una pausa para establecer
\(δ_2=min\{ϕ(x_i,x_{i−1}):(x_{i−1},x_i)\)un borde hacia atrás de\(P\)}.
Ya que se usa cada borde hacia atrás,\(δ_2>0\) siempre que sea necesario definirlo. Entonces establecemos\(δ=min\{δ_1,δ_2\}\).
En cualquier caso, ahora tenemos un número positivo\(δ\) y hacemos la siguiente observación elemental, para lo cual se le pide que proporcione una prueba en el Ejercicio 13.7.4.
Supongamos que tenemos un camino de aumento\(P=(x_0,x_1,…,x_m)\) con\(δ>0\) calculado como arriba. Modifique el flujo\(ϕ\) cambiando los valores a lo largo de los bordes de la ruta\(P\) en una cantidad que sea\(+δ\) o de\(−δ\) acuerdo con las siguientes reglas:
- Aumentar el flujo a lo largo de los bordes de los\(P\) cuales están hacia adelante.
- Disminuir el flujo a lo largo de los bordes de los\(P\) cuales están hacia atrás
Entonces la función resultante\(\hat{ϕ}\) es un flujo y tiene valor\(δ\).
El flujo de red que se muestra en la Figura 13.2 tiene muchas trayectorias de aumento. Ya vimos dos de ellos en el Ejemplo 13.6, al que llamamos\(P_1\) y\(P_3\) a continuación. En la lista a continuación, asegúrese de entender por qué cada ruta es una ruta creciente y cómo\(δ\) se determina el valor de para cada ruta.
- \(P_1=(S,F,A,T)\)con\(δ=12\). Todos los bordes están hacia adelante.
- \(P_2=(S,B,A,T)\)con\(δ=8\). Todos los bordes están hacia adelante.
- \(P_3=(S,E,D,C,B,A,T)\)con\(δ=9\). Todos los bordes están hacia adelante, excepto\((C,B)\) que es hacia atrás.
- \(P_4=(S,B,E,D,C,A,T)\)con\(δ=2\). Todos los bordes son hacia adelante, excepto\((B,E)\) y\((C,A)\) que están hacia atrás.
En el Ejercicio 13.7.7, se le pide que actualice el flujo de la Figura 13.2 para cada una de estas cuatro rutas individualmente.
13.3.1 Precaución en el aumento de caminos
Bob se ha vuelto muy bueno en el uso de rutas de aumento para aumentar el valor de un flujo de red. Todavía no está seguro de cómo encontrarlos, pero sabe algo bueno cuando lo ve. Se inclina a pensar que cualquier camino de aumento será un buen negocio en su búsqueda de un flujo de valor máximo. Carlos está satisfecho con el entusiasmo de Bob por los flujos de red, pero está empezando a pensar que debería advertir a Bob sobre los peligros de usar cualquier camino antiguo de aumento para actualizar un flujo de red. Coinciden en que la mejor situación es cuando el número de actualizaciones que hay que hacer es pequeño en cuanto al número de vértices en la red y que el tamaño de las capacidades en los bordes y el valor de un flujo máximo no deben tener un papel en el número de actualizaciones.
Bob dice que no puede ver de ninguna manera que las capacidades de borde puedan crear una situación en la que una red con solo unos pocos vértices requiera muchas actualizaciones, Carlos está pensando que un ejemplo está en orden. Le pide a Bob que escoja su entero muy grande favorito y que lo llame\(M\). Luego dibuja la red en cuatro vértices que se muestran en la Figura 13.9. Bob reconoce rápidamente que el valor máximo de un flujo en esta red es\(2M\). Lo hace usando el flujo con\(ϕ(S,A)=M, ϕ(A,T)=M, ϕ(S,B)=M, ϕ(B,T)=M\) y\(ϕ(A,B)=0\). Carlos está satisfecho con el trabajo de Bob.
Como esta red es realmente pequeña, fue fácil para Bob encontrar el flujo máximo. Sin embargo, Bob y Carlos coinciden en que “mirar” no es un enfoque que escale bien a redes más grandes, por lo que necesitan tener un enfoque para encontrar ese flujo usando caminos aumentadores. Bob le dice a Carlos que le dé un camino de aumento, y él hará la actualización. Carlos sugiere el camino de aumento\((S,A,B,T)\), y Bob lo determina\(δ=1\) para este camino de aumento. Actualiza la red (comenzando desde el flujo cero, es decir, con\(ϕ(e)=0\) para cada borde\(e\)) y ahora tiene valor 1. Bob le pide a Carlos otro camino de aumento, así que Carlos le da\((S,B,A,T)\). Ahora\((B,A)\) es atrasado, pero eso no fasea a Bob. Realiza la actualización, obteniendo un flujo de valor 2 con\((A,B)\) vacío nuevamente.
A pesar de la esperanza de Carlos de que Bob ya pudiera ver hacia dónde se dirigía esto, Bob pide ansiosamente otro camino de aumento. Carlos le da puntualmente\((S,A,B,T)\), lo que de nuevo tiene\(δ=1\). La actualización de Bob les da un flujo de valor 3. Antes de que Carlos pueda sugerir otro camino de aumento, Bob se da cuenta de cuál es el problema. Señala que Carlos sólo puede darle\((S,B,A,T)\) otra vez, lo que seguirá teniendo\(δ=1\) y dará como resultado que el valor del flujo aumente a 4. Dice que podrían seguir alternando entre esos dos caminos de aumento, aumentando el valor del flujo en 1 cada vez, hasta que hubieran hecho\(2M\) actualizaciones para finalmente tener un flujo de valor\(2M\). Dado que la red solo tiene cuatro vértices y\(M\) es muy grande, se da cuenta de que usar cualquier camino antiguo de aumento definitivamente no es una buena idea.
Carlos deja a Bob para tratar de encontrar un mejor enfoque. Se da cuenta de que a partir del flujo cero, solo necesitaría los caminos de aumento\((S,A,T)\) y\((S,B,T)\), cada uno con\(δ=M\) para obtener rápidamente el flujo máximo. Sin embargo, no está seguro de por qué un algoritmo debería encontrar que esos caminos aumentadores sean preferibles. Acerca de este tiempo, Dave deambula y murmura algo sobre los mejores caminos de aumento usando solo dos bordes, mientras que los dos caminos de aumento malvados de Carlos usaban tres cada uno. Bob piensa que tal vez Dave está en algo, así que decide volver a leer su libro de texto.