Grafos

República Bolivariana de Venezuela
Ministerio del Poder Popular para la Defensa
Universidad Nacional Experimental Politécnica de la Fuerza
Armada Nacional
Núcleo Guárico - Extensión Zaraza

Zaraza, junio 2012
REDES DE FLUJO
Una red de flujo es un grafo dirigido donde existen dos vértices especiales, uno llamado fuente, al que se le asocia un flujo positivo y otro llamado sumidero quetiene un flujo negativo y a cada arista se le asocia cierta capacidad positiva. En cada vértice diferente a los dos especiales se mantiene la ley de corrientes de Kirchoff, en donde la suma de flujos entrantes a un vértice debe ser igual a la suma de flujos que salen de él. Puede ser utilizada para modelar el tráfico en un sistema de autopistas, fluidos viajando en tuberías, corrientes eléctricasen circuitos eléctricos o sistemas similares por lo que viaje algo entre nodos.
Las redes de flujo son modelos matemáticos aplicables a situaciones tales como: sistemas de tuberías (para fluidos como agua, petróleo o gas), redes de cableado eléctrico, sistemas de carreteras, sistemas de transporte de mercancías, etc. La de noción formal es la siguiente:

Una red de flujo es un dígrafo G =(V;E) con una función de capacidad c : E ->R+ y dos vértices distinguidos, llamados fuente y sumidero.

Redes de Flujo estables

Redes de Flujo salientes

Redes de Flujo entrantes

Redes de Flujo neto.

Es posible trabajar simplemente sobre flujos netos entre vértices ya que sigamos verificando todas las restricciones con flujos netos: se define entonces un flujo neto sobre una red deflujo como una función:

Y lo importante: las dos definiciones son equivalentes entonces se puede resolver el problema de flujo máximo con esa representación

Usar la misma representación de arcos que para los grafos dirigidos ponderados, añadiendo: flujo, capacidad métodos para: estimar la capacidad residual, que sirve mucho en la búsqueda de un flujo máximo aumentar un flujo dado
Mejor usarrepresentación por grafo no dirigido: necesitamos en cada vértice a la vez los arcos entrantes Y los arcos salientes (arcos doblemente presentes).

Redes de Flujo de Costo Mínimo:

Bi>0 si i es un nodo origen.
Bi<0 si i es un nodo destino.
Bi=0 si i es un nodo de transbordo.
Una condición necesaria para que el modelo tenga solución factible es que +(bi=0), es decir, que el flujo totalgenerado en los nodos origen  sea igual al flujo total absorbido por los nodos destino.

Cuando esta condición no se cumple (problemas de transporte no balanceado en los que la oferta es diferente a la demanda) se generan nodos ficticios que generen o que absorban flujo. Los costos asociados a los arcos que parten o llegan a estos nodos son cero.
 Con frecuencia bit y que sonvalores enteros. Las variables x son variables enteras y no se requiere agregar esta  condición al modelo. (un modularidad).
Con este modelo es posible plantear un problema de transporte, de transbordo, de flujo máximo y de camino más corto.

Cadena de incremento de flujos
Supongamos que tenemos un camino de s a t un camino legal siguiendo las direcciones de las flechas, tal que en   cada arco delcamino el flujo existente no ocupa toda la capacidad del arco que hay margen en cada arco para aumentar el flujo (s=v0!v1!v2!v5=t).
Sumamos  el mínimo de los márgenes m al flujo de cada arco del camino el nuevo flujo f0 así construido es válido y tiene mayor valor ,val(f0)=val(f)+m>val(f). el camino de s a t que hemos tomado será por tanto un camino aumentador del flujo. Pero puede ocurrirque no dispongamos de estos caminos y sin embargo el flujo pueda aumentarse. Con el nuevo flujo obtenido sobre la red no podemos encontrar otro camino aumentador, pues no podemos aumentar yendo desde s por v1, y tampoco con el camino s!v3!v4!.Existe otra posibilidad, que es considerar recorridos “sin tener en cuenta el sentido de las flechas (que serán caminos no legales, pero validos para...