13.2: Flujos y Cortes
- Page ID
- 118245
Considerando las aplicaciones sugeridas al inicio del capítulo, es natural pedir el valor máximo de un flujo en una red dada. Dicho de otra manera, queremos encontrar el mayor número\(v_0\) para que exista un flujo\(ϕ\) de valor\(v_0\) en la red. Por supuesto, no sólo queremos encontrar el valor máximo\(v_0\), sino que también queremos encontrar un flujo\(ϕ\) que tenga este valor. Aunque pueda parecer un poco sorprendente, desarrollaremos un algoritmo eficiente que encuentre un flujo de valor máximo y encuentre un certificado que verifique la afirmación de optimalidad. Este certificado hace uso del siguiente concepto importante.
Una partición\(V=L \cup U\) del conjunto de vértices\(V\) de una red con\(S \in L\) y\(T \in U\) se llama corte. La capacidad de un corte\(V=L \cup U\), denotada\(c(L,U)\), se define por
\(c(L,U)=\displaystyle \sum_{x \in L, y \in U} c(x,y)\).
Dicho de otra manera, la capacidad del corte\(V=L \cup U\) es la capacidad total de todos los bordes desde\(L\) hasta\(U\). Tenga en cuenta que al computar la capacidad del corte\(V=L \cup U\), solo agregamos las capacidades de los bordes de\(L\) a\(U\). No incluimos los bordes de\(U\) a\(L\) en esta suma.
Volvamos a echar un vistazo a la red en la Figura 13.2. Consideremos primero el corte\(V=L_1 \cup U_1\) con
\(L_1=\{S,F,B,E,D\}\)y\(U_1=\{A,C,T\}\).
Aquí vemos que la capacidad del corte es
\(c(L_1,U_1)=c(F,A)+c(B,A)+c(B,C)+c(D,C)=24+15+20+42=101\).
Debemos ser un poco más cuidadosos, sin embargo, cuando miramos el corte\(V=L_2 \cup U_2\) con
\(L_2=\{S,F,B,E\}\)y\(U_2=\{A,D,C,T\}\).
Aquí la capacidad del corte es
\(c(L_2,U_2)=c(F,A)+c(B,A)+c(B,C)+c(E,D)=24+15+20+20=79\).
Observe que no incluimos\(c(D,B)\) en el cálculo ya que el borde dirigido\((D,B)\) es de\(U_2\) a\(L_2\).
La relación entre flujos y cortes se basa en el siguiente teorema fundamentalmente importante.
Dejar\(G=(V,E)\) ser una red, dejar\(ϕ\) ser un flujo en\(G\), y dejar\(V=L \cup U\) ser un corte. El valor del flujo es como máximo tan grande como la capacidad del corte.
- Prueba
-
En esta prueba (y a lo largo del capítulo), adoptamos la convención muy razonable de que\(ϕ(x,y)=0\) si no\((x,y)\) es un borde dirigido de una red\(\textbf{G}\).
Dejar\(ϕ\) ser un flujo de valor\(v_0\) y dejar\(V=L \cup U\) ser un corte. Primer aviso que
\(v_0= \displaystyle \sum_{y \in V} ϕ(S,y)−\sum_{z \in V} ϕ(z,S)\),
ya que la segunda suma es .0. Además, para la segunda de nuestras leyes de conservación de flujo, tenemos para cualquier vértice que no sea la fuente y el sumidero,
\(\displaystyle \sum_{y \in V}ϕ(x,y)− \sum_{z \in V}ϕ(z,x)=0\).
Ahora tenemos
\(v_0= \displaystyle \sum_{y \in V}ϕ(S,y) - \sum_{z \in V}ϕ(z,S)\)
\(= \displaystyle \sum_{y \in V} ϕ(S,y) - \sum_{z \in V}ϕ(z,S) + \sum_{x \in L \\ x \neq S}[\sum_{y \in V} ϕ(x,y) - \sum_{z \in V}ϕ(z,x)]\)
\( = \displaystyle \sum_{x \in L} [ \sum_{y \in V} ϕ(x,y) - \sum_{z \in V} ϕ(z,x)]\)
En este punto, queremos hacer una pausa y mirar la última línea. Observe que si\((a,b)\) es un borde dirigido con ambos puntos finales adentro\(L\), entonces cuando se realiza la suma externa para\(x=a\), obtenemos una contribución general de\(ϕ(a,b)\). Por otro lado, cuando se realiza para\(x=b\), obtenemos un aporte de\(−ϕ(a,b)\). Así, los términos se cancelan y todo se simplifica a
\(\displaystyle \sum_{x \in L \\ y \in U} ϕ(x,y) - \sum_{x \in L \\ z \in U} ϕ(z,x) \leq \sum_{x \in L \\ z \in U} ϕ(x,y) \leq \sum_{x \in L \\ y \in U} c(x,y) = c(L,U)\).
Por lo tanto\(v_0 \leq c(L,U)\).
A Bob le está dando un poco de sensación de déjà vu después de leer el Teorema 13.4. Él recuerda del Capítulo 5 que el tamaño máximo de una camarilla en una gráfica es siempre como mucho el número mínimo de colores requeridos para colorear correctamente la gráfica. No obstante, también recuerda que hay gráficas sin camarillas de talla tres pero con número cromático arbitrariamente grande, por lo que no tiene demasiadas esperanzas de que este teorema vaya a ayudar mucho aquí. Yolanda interviene con un recordatorio del Capítulo 6, donde aprendieron que el tamaño máximo de una anticadena en un poset es igual al número mínimo de cadenas en las que se puede particionar el conjunto de tierra del poset. Alice señala que la afirmación de Yolanda sigue siendo cierta si se intercambian las palabras “cadena” y “anticadena”. Esto provoca un intenso debate sobre si el valor máximo de un flujo en una red debe ser siempre igual a la capacidad mínima de un corte en esa red. Después de un tiempo, Carlos sugiere que seguir leyendo podría ser la mejor idea para resolver su debate.