Maximum Flow

El problema del máximo flujo parte de la necesidad de saber cuanto es la mayor cantidad de producto que puede ser enviado a través de ciertos puntos o canales, partiendo desde la fabrica misma hacia algún almacén. Imaginemos una fabrica $s$ que produce cajas, y esta envía a través de sus camiones cierto numero de ellas, a cada una de sus otras cedes $v_{1},v_{2}...v_{k}$  hasta llegar u un almacén digamos $t$, como los camiones viajan sobre rutas especificas (aristas) entre las otras cedes (vértices) y tienen una capacidad $c(u,v)$ cajas por día entre cada par de cedes $u$ y $v$. El objetivo es determinar el numero mas grande $p$ de cajas por día que puede ser embarcadas y luego producir esta cantidad, ya que no hay razón para producir mas que las que pueden ser almacenadas. También estamos interesados en optimizar el envío de tal manera que no haya acumulaciones en cada cede, es decir que la cantidad cajas que entran en una cede debe ser la misma a la que sale.

Se presentara el Método de Ford-Fulkerson para resolver el problema del flujo máximo.

Llamamos método en lugar de algoritmo ya que abarca varias implementaciones con diferentes tiempos de funcionamiento.

El método depende de 3 ideas.

• Redes Residuales 
• Trayectorias de aumento 
• Cortes

Importantes para el teorema del Máximo Flujo-Mínimo Corte, que mostraremos mas adelante.

El método de Ford-Fulkerson es iterativo.

• Se comienza con un $f(u,v)=0$  $\forall u,v\inV$
• Se un flujo inicial de cero.
• En cada iteración se aumenta el valor el valor del flujo mediante una búsqueda de una trayectoria de aumento. Que podemos pensar simplemente como un camino de $s$ a $t$ del cual se puede enviar un mayor flujo y así aumentar el flujo de este camino.
• Se repite el proceso hasta ya no encontrar caminos a aumentar que se pueda encontrar.

En otras palabras la idea es seleccionar repetidas veces cualquier trayectoria de $s$ a $t$ y asignamos el flujo maximo en esta trayectoria.

Asi como nosotros podemos modelar un mapa vial como un grafo dirigido para encontrar el camino mas corto. Nosotros tambien podemos interpretar un grafo dirigido como una "red de flujos" y usamos esto para responder problemas acerca de flujo de materiales.

Red de Flujo: Es un grafo dirigido $G(V,E)$ en el cual cada arista $(u,v)\inE$ tiene una capacidad positiva $c(u,v)\geq0$ $c:E \rightarrow R\cup\{0\}$. Si $(u,v)\nothinE$ asumimos que $c(u,v)=0$. Llamaremos a los vértices fuente y sumidero como $s$ y $t$ respectivamente.

Para conveniencia asumiremos que todo vértice se encuentra sobre algún camino de $s$ a $t$ esto es para todo $v\inV$ hay un camino tal que $s \rightsquigarrow v \rightsquigarrow t$

Un flujo en e $G$ es una función de valor real $f:V \times V \rightarrow R$ que satisface las siguientes tres propiedades :

• Capacidad restringida: $\forall u,v \in V$ se requiere $f(u,v) \leqslant c(u,v)$
• Simetría Oblicua: $\forall u,v \in V$ se requiere $f(u,v) = -f(v,u)$
• Flujo de conservación: $\forall u,v \in V-\{s,t\}$ se requiere $\sum_{v \in V}f(u,v)=0$

El flujo neto de una fuente es una cantidad que puede ser positiva o negativa.

 

El valor del flujo $f$ es definido por :$|f|=\sum_{v \in V}f(s,v)$. Esto denota el valor de la fuente no debemos confundir con valor absoluto.  Aun lo estoy editando... disculpas a la comunidad...