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...

Bellman-Ford Algorithm

Uno de los algoritmos indicados para resolver el problema de los caminos mas cortos desde una fuente a múltiples destinos, podría ser el de Bellman-Ford. A diferencia del algoritmo de Dijkstra, Bellman-Ford puede ser aplicado en grafos con ciclos negativos.  Generalmente, este algoritmo encuentra los caminos mas cortos de una fuente $s \in V$ para todo $v \in V$ en un grafo $G(V,E)$ o determina que existe un ciclo de peso negativo alcanzable por la fuente.

Si un grafo $G(V,E)$ contiene un ciclo de peso de negativo entoces el camino mas corto no existe.

Veamos lo siguiente...

Supóngase que tenemos el siguiente grafo. 

Este grafo contiene un ciclo $c=<u,r,u>$ donde su peso  es $w(c)=w(u,r)+w(r,u)=-2\leq0$ es negativo, ademas de esto es alcanzable por la fuente $s$. Si tomamos el siguiente camino  $p=<s,u,r,u,v>$ para llegar a $v$ este seria un camino de peso $w(p)=1$, sin embargo como $c$ es un ciclo, si tomamos el siguiente camino $p_{1}=<s,u,r,u,r,u,v>$ entonces el nuevo peso es $w(p_{1})=-1$, si $p_{2}=<s,u,r,u,r,u,r,u,v>$ tendremos que su peso es igual a $-3$ y así sucesivamente si vamos tomando nuevos camino por el ciclo podemos hallar siempre un camino mas corto hacia $v$ hasta $-\infty$, lo que causa que este no exista.

El siguiente código muestra el algoritmo de Bellman-Ford.

Ahora para el grafo dado en la figura de abajo, tenemos la siguiente tabla, que muestra la corrida del algoritmo.

La ultima iteración muestra el tamaño del camino mas corto para llegar de $s$ a los demás vértices, teniendo en cuenta el orden de las aristas anterior. 

Cabe aclarar que este orden es arbitrario y podemos tomar el que mas nos crea conveniente.

El siguiente teorema muestra que Bellman-Ford corre correctamente.

Primero veamos los siguientes lemas.

Lema1

 Sea $s \rightsquigarrow u \rightarrow v $es un camino mas corto y si $d[u]=\delta(s,u)$ entonces $d[v]=\delta(s,v)$ después de la relajación.

Lema

Si $G(V,E)$ no contiene ciclos negativos alcanzables por $s$. Entonces en la terminación de Bellman-Ford $d[v]=\delta(s,v)$ para todo $v$ alcanzable por $s$.

Prueba

Sea $v$ un vértice alcanzable por $s$, sea $p=<v_{0},...,v_{k}>$ un camino mas corto de $s$ a $v$ donde $v_{0}=s$ y $v_{k}=v$ y tiene el menor numero de aristas posibles. (p es un camino simple sin ciclos, es decir no se repiten vértices).

Inducción

• $d[v_{0}]=0=\delta(s,v_{0})=\delta(s,s)=0$ después de la inicialización esta igualdad se mantiene.
• (Hipótesis de inducción): $d[v_{i-1}]=\delta(s,v_{i-1})$ después de $i-1$ pasos.
• Veamos que $d[v_{i}]=\delta(s,v_{i})$ si aplicamos el método RELAX a la arista $(v_{i-1},v_{i})$ en el paso $i$ entonces como $p$ es un camino mas corto y el lema1, $d[v_{i}]=\delta(s,v_{i})$ 

Teorema

Supongamos que $G$ no contiene ciclos de peso negativo. Entonces por el lema anterior $d[v]=\delta(s,v)$ entonces veamos que el algoritmo de Bellman-Ford retorna ''true".  Y si $G$ tiene algún ciclo negativo entonces retorna ''false''.

 

Prueba

En la terminación $d[v]=\delta(s,v)\leq\delta(s,u)+w(u,v)=d[u]+w(u,v)$ por desigualdad triangular y lema anterior.

Ahora por lo anterior tenemos que $d[v]\leqd[u]+w(u,v)$ para cada arista $(u,v)$ en $E$ esto muestra que la linea $6$ del algoritmo falla, luego retorna ''true''.

Ahora para la segunda parte, tenemos que $G$ contiene un ciclo negativo digamos $c=<v_{0},...,v_{k}>$ donde $v_{0}=v_{k}$ alcanzable por $s$, entonces $\sum_{i=1}^{k}w(v_{i-1},v_{i})<0$. Supóngase que Bellman-Ford retorna ''true" Esto es $d[v_{i}]\leqd[v_{i-1}]+w(v_{i-1},v_{i})$ para $i=1,...,k.$

Entonces $$\sum_{i=1}^{k}d[v_{i}]\leq\sum_{i=1}^{k}d[v_{i-1}]+\sum_{i=1}^{k}w(v_{i-1},v_{i})$$ 

Luego como $\sum_{i=1}^{k}d[v_{i}]=\sum_{i=1}^{k}d[v_{i-1}]$ porque cada vértice aparece una sola vez en cada ciclo de cada suma.

Por tanto $0\leq\sum_{i=1}^{k}w(v_{i-1},v_{i})$ pero esto contradice que el ciclo sea de peso negativo mostrado anteriormente. Luego retorna '''false'.

Nos vemos en otra ocasión.

Minimum Spanning Tree

En el diseño de circuitos electrónicos, a menudo tenemos la necesidad de interconectar un conjunto de pines o pernos por medio de algún tipo de cableado eléctrico, de tal forma que todos estén conectados entre si. Si tenemos un conjunto de $n$ pines, podríamos usar $n-1$ cables para la conexión de cada dos pines. Sin embargo, de todas las conexiones posibles la que utiliza la menor cantidad de cable suele ser la mas deseable.

Nosotros podemos modelar este cableado con un grafo conexo no dirigido $G(V,E)$ donde $V$ es el conjunto de pines y $E$ el conjunto de posibles interconexiones entre pares de pines

Ya que $T$ es acíclico y conecta todos los vértices este debe formar un árbol, el cual llamaremos árbol de expansión y el árbol con peso total mínimo, árbol de mínima expansión.

Nosotros llamaremos el problema de determinar el árbol $T$, problema de árbol de mínima expansión. 

Existen dos algoritmos que nos ayudan a resolver este tipo de problemas el algoritmo de Kruskal y el Algoritmo de Prim, cada uno fácilmente puede correr en un tiempo $O(\|E\|lg\|V\|)$ usando binary heaps ordinarios, aunque el algoritmo de Prim puede ser mas rápido si usamos Fibonacci Heaps en un tiempo de $O(\|E\| + \|V\|lg\|V\|)$.

Estos dos algoritmos usan la heurística de optimización llamada estrategia "Greedy". La cual consiste (tomada de Wikipedia, pues me pareció que estaba muy bien explicado) en escoger en cada paso al mejor elemento $x\inC$ posible, conocido como el elemento más prometedor. Se elimina ese elemento del conjunto de candidatos $(C\leftarrowC-\{x\})$ y, acto seguido, comprueba si la inclusión de este elemento en el conjunto de elementos seleccionados $(S\cup \{x\})$ produce una solución factible.

En caso de que así sea, se incluye ese elemento en $S$. Si la inclusión no fuera factible, se descarta el elemento. Iteramos el bucle, comprobando si el conjunto de seleccionados es una solución y, si no es así, pasando al siguiente elemento del conjunto de candidatos.

Una vez finalizado el bucle, el algoritmo comprueba si el conjunto $S$es una solución o no, devolviendo el resultado apropiado en cada caso.

Los algoritmos de Kruskal y Prim hacen uso de una regla muy particular y es la regla de encontrar "safe edges", pero antes de empezar a definir que es una "safe edge", veamos algunas definiciones y generalidades.
y para cada arista $(u,v) \in E$ nosotros especificamos un peso $w(u,v)$ que indica el monto de cable necesitado para conectar $u$ a $v$. Nosotros deseamos encontrar un conjunto $T \subseteq E$ acíclico que conecte todos los vértices y cuyo peso total sea el mas mínimo posible.

 

Un corte $(S,V-S)$ de un grafo no dirigido $G(V,E)$ es una particion de $V$.

Nosotros decimos que una arista $(u,v)$ cruza el corte  $(S,V-S)$ si y solo si  los extremos están uno en $S$  y el otro en $V-S$

Decimos que un corte $(S,S-V)$ respeta un conjunto $A$ de aristas, si ninguna arista en $A$ cruza el corte.

Una arista ligera es la arista que cruza el corte con menor peso.

Ahora nosotros definimos una "safe edge" como aquella arista mas prometedora, que puede ser adicionada a un conjunto $A$ contenido en un árbol de mínima expansión $T$.

Mas formalmente tenemos el siguiente teorema.
 Teorema:
 

Sea $G(V,E)$ un grafo conexo no dirigido con una función de valor real w definida sobre $E$. Sea $A$ un subconjunto de $E$, contenido en algún árbol de mínima expansión para G, sea $(S,V-S)$ algún corte que respete a $A$ y sea $(u,v)$ una arista ligera que cruza $(S,V-S)$, entonces $(u,v)$ es una "safe edge" para $A$.

Corolario:
 

Sea $G(V,E)$ un grafo conexo no dirigido con una función de valor real w definida sobre $E$. Sea $A$ un subconjunto de $E$, contenido en algún árbol de mínima expansión para $G$ y sea $C$ un componente conexo (árbol) en el bosque $G_{A}(V,A)$. Si $(u,v)$ es una arista ligera que conecta $C$ con algun otro componente en $G_{A}$, entonces $(u,v)$ es una "safe edge" para $A$.

En forma genérica el algoritmo se basa en lo siguiente:

 

Kruskal y Prim son elaboraciones de este algoritmo, sin embargo cada uno tiene su propia forma de determinar una "safe edge" enunciada en la linea 3 del GENERIC-MST.

En Kruskal (que es el que describiremos a continuación) el conjunto A es un bosque y la "safeedge" que es añadida a A es siempre la arista de menor peso que une dos componentes disjuntos del grafo. En el algoritmo de Prim el conjunto A forma un solo árbol y la "safe edge" que es añadida a A es siempre la arista de menor peso que conecta el árbol a un vértice que no esta en el árbol.

Algoritmo de Kruskal.  

Como habíamos mencionado el algoritmo de Kruskal se basa directamente en el algoritmo genérico del minimun spanning tree . Kruskal para encontrar una "safe edge" se basa en el corolario antes mencionado, este encuentra la "safe edge" a adicionar en el bosque de aumento $A$ buscando todas las aristas que conecten dos arboles en el bosque, tomando la de menor peso. Sin perdida de generalidad sea $C_{1}$y $C_{2}$ dos arboles conectados por una arista $(u,v)$, si $(u,v)$ es la arista de menor peso esta debe ser una arista ligera que conecta $C_{1}$ a algún árbol, y por el corolario esto implica que (u,v) es una "safe edge" para C1. Kruskal es un algoritmo "greedy" porque en cada paso este añade a al árbol la arista de menor peso posible.

A continuación mostremos una implementación sencilla del mismo. Esta implementación hace uso de las funciones de la estructura de datos de conjuntos disjuntos,  como por ejemplo la función FIND-SET() y UNION(). En esta estructura cada conjunto contiene un elemento que lo representa. La operación FIND-SET(u) retorna el elemento representativo del conjunto que contiene a u, mientras que UNION(u,v) une los conjuntos de los cuales u y v son representantes y destruye a cada conjunto, dejando como representante a alguno de los dos u o v del nuevo conjunto unido, en este caso tomaremos como representante a v.

Ejemplo: Hallar el árbol de mínima expansión en el siguiente grafo.

 

Una manera eficiente de correr nuestro algoritmo es haciendo una tabla, donde se muestre el orden no decreciente de las aristas, ya saben que se hace según el peso de la misma, y vamos observando que sucede en cada paso con la $UNION(u,v)$ y nuestro conjunto $A$, como se muestra a continuación:  

 

 

Finalmente el conjunto $A$ es retornado dando como resultado el siguiente árbol de mínima expasión:

 

$A=\{(h,g),(c,i),(f,g),(a,b),(c,f),(a,h),(d,e)\}$

 

 

Hasta entonces espero les haya gustado...

Single-Source Shortest Paths

Hola amigos, nuevamente estoy por aquí compartiendo nuevas experiencias acerca del curso. El blog estaba un poco abandonado, pero ya estoy de vuelta.

El día de hoy, compartiré el tema que me toco exponer en mi clase de Análisis de Algoritmos. Escogí este tema porque siempre he tenido un gusto por los grafos. El tema se titula "Caminos mas cortos desde un origen a múltiples destinos". El camino mas corto es un problema clásico en la teoría de grafos y se han propuesto un gran numero de diferentes soluciones. Por lo general, inicialmente tenemos un grafo $G=(V,E)$ donde $V$ es el conjunto de vértices de los cuales pueden representar ciudades, estados, maquinas etc. y un conjunto $E$ de aristas las cuales se le asignan ciertos pesos que representan por ejemplo, distancias entre sitios, tiempos de separación entre ciertas tareas ejecutadas, costos de la transmisión de información entre localidades, etc. El problema del camino mas corto tiene muchas variantes, desde hallar el camino mas corto a partir de un vértice fuente a un vértice destino, a hallar todos los caminos mas cortos entre cada par de vértices del grafo. En este caso el problema que discutiremos es, hallar los caminos mas cortos desde un vértice fuente a todos los demás vértices que componen el grafo.

Antes de presentar los algoritmos que nos permitirán dar una solución a este  problema y dar un breve ejemplo del mismo, se mostraran algunas generalidades  importantes, que debemos tener en cuenta en esta teoría...

Formalmente...

Sea un grafo dirigido $G(V,E)$ ponderado, con una función de peso  

$w:E \rightarrow R$ que asigna a las arista pesos de valor real.

El peso de un camino $p=<v_{0},v_{1},...,v_{k}>$ es la suma de 

los pesos de las aristas que lo componen:

$w(p)=\sum_{i=1}^{k}w(v_{i-1},v_{i})$

El peso del camino mas corto de $u$ a $v$ por
$\delta(u,v)=\left\{\begin{array}{cl}min\{w(p): \stackrel{p}{u \rightsquigarrow v}\} & \mbox{si existe un camino de u a v }\\ \infty &\mbox{otro caso}\end{array}\right.$ 

El camino mas corto de un vértice $u$ a otro $v$ 
esta definido por algún camino $p$ tal que
$w(p)=\delta(u,v)$ 
En otras palabras el camino de mínimo peso de $u$ a $v$

Ahora podemos definir el problema de los caminos mas cortos desde un origen a varios destinos como: Dado un grafo $G(V,E)$ nosotros queremos encontrar los caminos mas cortos desde un vértice origen $s \in V$ A cada vértice $v \in V$

Algo que caracteriza a los algoritmos para encontrar caminos mas cortos o mas largos, es el paradigma de la Programación Dinámica, y este caso no es la excepción, sin embargo para usar esta técnica debemos primero establecer la una subestructura óptima.

Subestructura Óptima para caminos mas cortos: $$Un \ subcamino \ de \ un \ camino \ corto \ es \ tambien \ un \ camino \ corto $$

Ahora tenemos la siguiente propiedad...

Desigualdad Triangular:  

Para todo vértice $s, u , v \in V$, donde $s$ es una fuente

se tiene que $\delta(s,v) \leq \delta(s,u)+w(u,v)$

Hasta este punto hemos mencionado algunas generalidades que son de suma importancia para esta teoría de los caminos mas cortos.

Ahora para nuestro problema existen algoritmos que pueden dar solución a nuestro problema, uno de ellos es el algoritmo de Dijkstra y el de Bellman-Ford, donde su diferencia radica es en el grafo sobre el cual se esta ejecutando el algoritmo, ya que el de Dijkstra trabaja sobre grafos donde los pesos de las aristas todos son positivos, mas aun no tiene ciclos negativos alcanzados por $s$, a diferencia del algoritmo de Bellman-Ford que si permite pesos negativos en las aristas.

El que discutiremos el día de hoy es el algoritmo de Dijkstra el cual utiliza el método "Greedy Algorithms", y también una técnica muy interesante llamada relajación, en otro post, hablaremos un poco del Algoritmo de Bellman-Ford.

La idea principal es para el método Greedy Algorithm:

1. Un conjunto $S$ de vértices cuya distancia del camino mas corto desde $s$ es conocida.
2. En cada paso adicionamos un vértice $v \in V-S$ cuya distancia estimada es mínima, (este sera nuestro criterio de escogencia)
3. Guardar estas distancias estimadas de vértices adyacentes a $V$

La técnica de relajación de la que hace uso el procedimiento, consiste en atribuirle a cada vértice $v \in V$ una estimación  $d[]$ del peso del camino mas corto de $s$ a $v$, $d[]$  la denominaremos estimación del camino mas corto, ejemplo:

Supóngase que deseamos relajar la arista $(u,v)$ el procedimiento es el siguiente:

Previamente inicializamos, nuestro  grafo con estimaciones de infinito tomando esto como que nuestro camino mas corto es muy grande, el procedimiento es el siguiente:

El método de relajación para una arista $(u,v)$

Aquí $\pi[v]$ indica el predecesor de $v$. A continuación se muestra la relajación de la arista $(u,v)$ como ejemplo...

El Algoritmo de Dijkstra es el siguiente...

En el anterior  algoritmo $Q$ representa una cola de prioridad sobre las llaves guardadas y EXTRAMIN() extraerá el tamaño del camino mas corto por las condiciones de $Q$.

Aplicación del Algoritmo de Dijkstra...

Hacer una tabla con las estimaciones de los caminos mas cortos aveces resulta mas útil este es un ejemplo de cuando finaliza el algoritmo, donde los números con asterisco indican el peso del camino mas corto para llegar desde $s$ al vértice que lidera la columna:

Como ven para llegar de $s$ a $t$ tenemos un camino de peso 8, para llegar a $y$ un camino de peso 5, a $x$ de peso 9 y finalmente para llegar a $z$ un camino de peso 7.

Eso es todo amigos... nos vemos en una próxima edición.