5.11: Gráficas dirigidas
- Page ID
- 117083
Una gráfica dirigida, también llamada dígrafo, es una gráfica en la que los bordes tienen una dirección. Esto generalmente se indica con una flecha en el borde; más formalmente, si\(v\) y\(w\) son vértices, un borde es un par desordenado\(\{v,w\}\), mientras que un borde dirigido, llamado arco, es un par ordenado\((v,w)\) o\((w,v)\). El arco\((v,w)\) se dibuja como una flecha de\(v\) a\(w\). Si una gráfica contiene ambos arcos\((v,w)\) y\((w,v)\), esto no es un “borde múltiple”, ya que los arcos son distintos. Es posible tener múltiples arcos, es decir, un arco se\((v,w)\) puede incluir varias veces en el multiconjunto de arcos. Como antes, un dígrafo se llama simple si no hay bucles o múltiples arcos.
Denotamos por\(E\strut_v^-\) el conjunto de todos los arcos de la forma\((w,v)\), y por\(E_v^+\) el conjunto de arcos de la forma\((v,w)\). El indegree de\(v\), denotado\(\text{d}^-(v)\), es el número de arcos adentro\(E\strut_v^-\), y el outdegree\(\text{d}^+(v)\),, es el número de arcos adentro\(E_v^+\). Si los vértices son\(v_1,v_2,\ldots,v_n\), los grados generalmente se denotan\(d^-_1,d^-_2,\ldots,d^-_n\) y\(d^+_1,d^+_2,\ldots,d^+_n\). Tenga en cuenta que ambos\(\sum_{i=0}^n \text{d}^-_i\) y\(\sum_{i=0}^n \text{d}^+_i\) contar el número de arcos exactamente una vez, y por supuesto\(\sum_{i=0}^n \text{d}^-_i=\sum_{i=0}^n \text{d}^+_i\). Un paseo en un dígrafo es una secuencia\(v_1,e_1,v_2,e_2,\ldots,v_{k-1},e_{k-1},v_k\) tal que\(e_k=(v_i,v_{i+1})\); si\(v_1=v_k\), es un paseo cerrado o un circuito. Un camino en un dígrafo es un paseo en el que todos los vértices son distintos. No es difícil demostrar que, en cuanto a las gráficas, si hay un paseo de\(v\) a\(w\) entonces hay un camino de\(v\) a\(w\).
Muchos de los temas que hemos considerado para las gráficas tienen análogos en dígrafos, pero también hay muchos temas nuevos. Veremos un resultado particularmente importante en esta última categoría.
Definición\(\PageIndex{1}\): Network
Una red es un dígrafo con una fuente\(s\) y un destino designados\(t\not=s\). Además, cada arco\(e\) tiene una capacidad positiva,\(c(e)\).
Las redes pueden ser utilizadas para modelar el transporte a través de una red física, de una cantidad física como el petróleo o la electricidad, o de algo más abstracto, como la información.
Definición\(\PageIndex{2}\): Flow
Un flujo en una red es una función\(f\) desde los arcos del dígrafo hasta\(\mathbb{R}\), con\(0\le f(e)\le c(e)\) para todos\(e\), y tal que\[\sum_{e\in E_v^+}f(e)=\sum_{e\in E_v^-}f(e),\nonumber\] para todos los que no\(v\) sean\(s\) y\(t\).
Deseamos asignar un valor a un flujo, igual al flujo neto que sale de la fuente. Dado que la sustancia que se transporta no puede “recolectar” ni “originarse” en ningún vértice que no sea\(s\) y\(t\), parece razonable que este valor también sea el flujo neto hacia el objetivo.
Antes de probarlo, introducimos alguna nueva notación. Supongamos que\(U\) es un conjunto de vértices en una red, con\(s\in U\) y\(t\notin U\). \(\overset{\longrightarrow}{U}\)Sea el conjunto de arcos\((v,w)\) con\(v\in U\),\(w\notin U\), y\(\overset{\longleftarrow}{U}\) sea el conjunto de arcos\((v,w)\) con\(v\notin U\),\(w\in U\).
Teorema \(\PageIndex{1}\)
Para cualquier flujo\(f\) en una red, el flujo neto que sale de la fuente es igual al flujo neto hacia el objetivo, es decir,\[\sum_{e\in E_s^+} f(e)-\sum_{e\in E_s^-}f(e)= \sum_{e\in E_t^-} f(e)-\sum_{e\in E_t^+}f(e).\nonumber\]
- Prueba
-
Vamos a mostrar primero que para cualquiera\(U\) con\(s\in U\) y\(t\notin U\),\[\sum_{e\in E_s^+} f(e)-\sum_{e\in E_s^-}f(e)= \sum_{e\in\overset{\longrightarrow}{U}} f(e)-\sum_{e\in\overset{\longleftarrow}{U}}f(e).\nonumber\]
Considera lo siguiente:\[S=\sum_{v\in U}\left(\sum_{e\in E_v^+}f(e)-\sum_{e\in E_v^-}f(e)\right).\nonumber\] La cantidad\[\sum_{e\in E_v^+}f(e)-\sum_{e\in E_v^-}f(e)\nonumber\] es cero excepto cuando\(v=s\), por la definición de un flujo. Así, la suma entera\(S\) tiene valor\[\sum_{e\in E_s^+} f(e)-\sum_{e\in E_s^-}f(e).\nonumber\] Por otro lado, podemos escribir la suma\(S\) como\[ \sum_{v\in U}\sum_{e\in E_v^+}f(e)- \sum_{v\in U}\sum_{e\in E_v^-}f(e). \nonumber\] Cada arco\(e=(x,y)\) con ambos\(x\) y\(y\) en\(U\) aparece en ambas sumas, es decir, en\[\sum_{v\in U}\sum_{e\in E_v^+}f(e),\nonumber\] cuándo\(v=x\), y en\[\sum_{v\in U}\sum_{e\in E_v^-}f(e),\nonumber\] cuándo\(v=y\), y así el flujo en tales arcos contribuye\(0\) al valor general. Así, solo los arcos con exactamente un punto final en\(U\) hacen una contribución distinta de cero, por lo que toda la suma se reduce a\[\sum_{e\in \overset{\longrightarrow}{U} } f(e)-\sum_{e\in \overset{\longleftarrow}{U} }f(e).\nonumber\] Así\[\sum_{e=(s,v)} f(e)-\sum_{e=(v,s)}f(e)=S= \sum_{e\in \overset{\longrightarrow}{U} } f(e)-\sum_{e\in \overset{\longleftarrow}{U} }f(e),\nonumber\] como se desee.
Ahora vamos a\(U\) constar de todos los vértices excepto\(t\). Después\[ \sum_{e\in E_s^+} f(e)-\sum_{e\in E_s^-}f(e)= \sum_{e\in \overset{\longrightarrow}{U} } f(e)-\sum_{e\in \overset{\longleftarrow}{U} }f(e)= \sum_{e\in E_t^-} f(e)-\sum_{e\in E_t^+}f(e), \nonumber\] terminando la prueba.
Definición\(\PageIndex{3}\): Value
El valor de un flujo, denotado\(\text{val}(f)\), es\(\sum_{e\in E_s^+} f(e)-\sum_{e\in E_s^-}f(e)\). Un flujo máximo en una red es cualquier flujo\(f\) cuyo valor sea el máximo entre todos los flujos.
A continuación buscamos formalizar la noción de “cuello de botella”, con el objetivo de mostrar que el flujo máximo es igual a la cantidad que puede pasar por el cuello de botella más pequeño.
Definición\(\PageIndex{4}\): Cut
Un corte en una red es un conjunto\(C\) de arcos con la propiedad en la que cada ruta de\(s\) a\(t\) usa un arco en\(C\), es decir, si los arcos en se\(C\) eliminan de la red no hay ruta de\(s\) a\(t\). La capacidad de un corte, denotada\(c(C)\), es\[\sum_{e\in C} c(e).\nonumber\] Un corte mínimo es uno con capacidad mínima. Un corte\(C\) es mínimo si no se contiene correctamente ningún corte\(C\).
Tenga en cuenta que un corte mínimo es un corte mínimo. Claramente, si\(U\) es un conjunto de vértices que contienen\(s\) pero no\(t\), entonces\(\overset{\longrightarrow}{U}\) es un corte.
Lema \(\PageIndex{1}\)
Supongamos que\(C\) es un corte mínimo. Entonces hay un conjunto\(U\) que contiene\(s\) pero no\(t\) tal que\(C=\overset{\longrightarrow}{U}\).
- Prueba
-
Dejar\(U\) ser el conjunto de vértices\(v\) tal que haya un camino de\(s\) a\(v\) usando ningún arco en\(C\).
Supongamos que\(e=(v,w)\in C\). Dado que\(C\) es mínimo, hay un camino\(P\) de\(s\) a\(t\) usar\(e\) pero ningún otro arco en\(C\). Así, hay un camino de\(s\) a\(v\) usar ningún arco de\(C\), entonces\(v\in U\). Si hay un camino de\(s\) a sin\(w\) usar arco de\(C\), entonces este camino seguido por la porción de\(P\) que comienza con\(w\) es un paseo de\(s\) a sin\(t\) usar arco en\(C\). Esto implica que hay un camino desde\(s\) hasta no\(t\) usar arco en\(C\), una contradicción. Así\(w\notin U\) y así\(e\in \overset{\longrightarrow}{U}\). De ahí,\(C\subseteq \overset{\longrightarrow}{U}\).
Supongamos que\(e=(v,w)\in \overset{\longrightarrow}{U}\). Entonces\(v\in U\) y\(w\notin U\), así cada camino desde\(s\) hasta\(w\) usa un arco en\(C\). Ya que\(v\in U\), hay un camino de\(s\) a sin\(v\) usar arco de\(C\), y este camino seguido por\(e\) es un camino de\(s\) a\(w\). De ahí que el arco\(e\) deba estar en\(C\), entonces\(\overset{\longrightarrow}{U}\subseteq C\).
Ahora lo hemos demostrado\(C=\overset{\longrightarrow}{U}\).
Ahora podemos probar una versión del importante teorema de max-flow, min cut.
Teorema \(\PageIndex{2}\)
Supongamos que en una red todas las capacidades de arco son números enteros. Entonces el valor de un flujo máximo es igual a la capacidad de un corte mínimo. Además, hay un flujo máximo\(f\) para el que todos\(f(e)\) son enteros.
- Prueba
-
Primero mostramos que para cualquier flujo\(f\) y corte\(C\),\(\text{val}(f)\le c(C)\). Baste con mostrar esto para un corte mínimo\(C\), y por Lemma lo\(\PageIndex{1}\) sabemos\(C=\overset{\longrightarrow}{U}\) para algunos\(U\). Usando la prueba del Teorema\(\PageIndex{1}\) tenemos:\[ \text{val}(f) = \sum_{e\in\overset{\longrightarrow}{U}} f(e)-\sum_{e\in\overset{\longleftarrow}{U}}f(e) \le \sum_{e\in\overset{\longrightarrow}{U}} f(e) \le \sum_{e\in\overset{\longrightarrow}{U}} c(e) = c(\overset{\longrightarrow}{U}). \nonumber\] Ahora si encontramos un flujo\(f\) y cortamos\(C\) con\(\text{val}(f)=c(C)\), se deduce que\(f\) es un flujo máximo y\(C\) es un corte mínimo. Presentamos un algoritmo que producirá tal\(f\) y\(C\).
Dado un flujo\(f\), que inicialmente puede ser el flujo cero,\(f(e)=0\) para todos los arcos\(e\), haga lo siguiente:
- Vamos\(U=\{s\}\).
Repita los dos pasos siguientes hasta que no se agreguen nuevos vértices\(U\). - Si hay un arco\(e=(v,w)\) con\(v\in U\) y\(w\notin U\), y\(f(e)< c(e)\), agregar\(w\) a\(U\).
- Si hay un arco\(e=(v,w)\) con\(v\notin U\) y\(w\in U\), y\(f(e)>0\), agregar\(v\) a\(U\).
Cuando esto termine, ya sea\(t\in U\) o\(t\notin U\). Si\(t\in U\), hay una secuencia de vértices distintos\(s=v_1,v_2,v_3,\ldots,v_k=t\) tal que para cada uno\(i\),\(1\le i< k\), o bien\(e=(v_i,v_{i+1})\) es un arco con\(f(e)< c(e)\) o\(e=(v_{i+1},v_i)\) es un arco con\(f(e)>0\). Actualizar el flujo sumando\(1\) a\(f(e)\) para cada uno de los primeros, y restando\(1\) de\(f(e)\) para cada uno de los segundos. Este nuevo flujo\(f'\) sigue siendo un flujo: En el primer caso, desde\(f(e)< c(e)\),\(f'(e)\le c(e)\), y en el segundo caso, desde\(f(e)>0\),\(f'(e)\ge 0\). Es sencillo comprobar que para cada vértice\(v_i\),\(1< i< k\), que\[\sum_{e\in E_{v_i}^+}f'(e)=\sum_{e\in E_{v_i}^-}f'(e).\nonumber\] además,\(\text{val}(f')=\text{val}(f)+1\). Ahora\(f'\) renombrar a\(f\) y repetir el algoritmo.
Eventualmente, el algoritmo termina con\(t\notin U\) y fluye\(f\). Esto implica que para cada uno\(e=(v,w)\) con\(v\in U\) y\(w\notin U\),\(f(e)=c(e)\), y para cada uno\(e=(v,w)\) con\(v\notin U\) y\(w\in U\),\(f(e)=0\). La capacidad del corte\(\overset{\longrightarrow}{U}\) es\[\sum_{e\in\overset{\longrightarrow}{U}} c(e).\nonumber\] El valor del flujo\(f\) es\[ \sum_{e\in\overset{\longrightarrow}{U}} f(e)-\sum_{e\in\overset{\longleftarrow}{U}}f(e)= \sum_{e\in\overset{\longrightarrow}{U}} c(e)-\sum_{e\in\overset{\longleftarrow}{U}}0= \sum_{e\in\overset{\longrightarrow}{U}} c(e). \nonumber\] Así hemos encontrado un flujo\(f\) y corte\(\overset{\longrightarrow}{U}\) tal que\[ \text{val}(f) = c(\overset{\longrightarrow}{U}), \nonumber\] como se desee.
- Vamos\(U=\{s\}\).
El teorema max-flow, min-cut es cierto cuando las capacidades son números reales positivos, aunque por supuesto el valor máximo de un flujo no necesariamente será un número entero en este caso. Es algo más difícil de probar, requiriendo una prueba que implique límites.
Ya hemos probado que en una gráfica bipartita, el tamaño de una coincidencia máxima es igual al tamaño de una cubierta mínima de vértice, Teorema 4.6.4. Esto resulta ser esencialmente un caso especial del teorema max-flow, min-cut.
Corolario \(\PageIndex{1}\)
En una gráfica bipartita\(G\), el tamaño de una coincidencia máxima es el mismo que el tamaño de una cubierta mínima de vértice.
- Prueba
-
Supongamos que las partes de\(G\) son\(X=\{x_1,x_2,\ldots,x_k\}\) y\(Y=\{y_1,y_2,\ldots,y_l\}\). Crea una red de la siguiente manera: introduce dos nuevos vértices\(s\)\(t\) y arcos\((s,x_i)\) para todos\(i\) y\((y_i,t)\) para todos\(i\). Para cada borde\(\{x_i,y_j\}\) adentro\(G\), deja\((x_i,y_j)\) ser un arco. Dejar\(c(e)=1\) para todos los arcos\(e\). Ahora el valor de un flujo máximo es igual a la capacidad de un corte mínimo.
Dejar\(C\) ser un corte mínimo. Si\((x_i,y_j)\) es un arco de\(C\), reemplázalo por arco\((s,x_i)\). Esto sigue siendo un corte, ya que cualquier camino desde\(s\) hasta\(t\) incluyendo\((x_i,y_j)\) debe incluir\((s,x_i)\). Así, podemos suponer que\(C\) contiene sólo arcos de la forma\((s,x_i)\) y\((y_i,t)\). Ahora es fácil ver que\[K=\{x_i\vert (s,x_i)\in C\}\cup\{y_i\vert (y_i,t)\in C\}\nonumber\] es una cubierta de vértice de\(G\) con el mismo tamaño que\(C\).
Dejar\(f\) ser un flujo máximo tal que\(f(e)\) sea un entero para todos\(e\), lo cual es posible por el teorema max-flow, min-cut. Considera el conjunto de aristas\[M=\{\{x_i,y_j\}\vert f((x_i,y_j))=1\}.\nonumber\] Si\(\{x_i,y_j\}\) y\(\{x_i,y_m\}\) están ambos en este conjunto, entonces el flujo de salida de vértice\(x_i\) es de al menos 2, pero solo hay un arco en\(x_i\),\((s,x_i)\), con capacidad 1, contradiciendo la definición de un flujo. De igual manera, si\(\{x_i,y_j\}\) y\(\{x_m,y_j\}\) están ambos en este conjunto, entonces el flujo hacia el vértice\(y_j\) es de al menos 2, pero solo hay un arco fuera de\(y_j\)\((y_j,t)\),, con capacidad 1, también una contradicción. Así\(M\) es un emparejamiento. Además, si\(U=\{s,x_1,\ldots,x_k\}\) entonces el valor del flujo es\[ \sum_{e\in\overset{\longrightarrow}{U}}f(e)-\sum_{e\in\overset{\longleftarrow}{U}}f(e)= \sum_{e\in\overset{\longrightarrow}{U}}f(e)=|M|\cdot1=|M|. \nonumber\] Así\(|M|=\text{val}(f)=c(C)=|K|\), así hemos encontrado una coincidencia y una cubierta de vértice con el mismo tamaño. Esto implica que\(M\) es una coincidencia máxima y\(K\) es una cobertura mínima de vértice.