UNIDAD Nº 6.REDES DE FLUJO

Entendiendo una red de flujo como un grafo dirigido, donde la fuente es quien produce o inicia el traspaso de algún material o producto por los arcos, estos últimos, vistos como caminos o conductos y tomando en cuenta la ley de corrientes de Kirchoff, donde, la suma de flujos entrantes a un vértice debe ser igual a la suma de flujos saliendo del vértice.
 

 


 

 DESCRIPCIÓN MATEMÁTICA:

Una red de flujo es un grafo dirigido G = (V,E) en donde cada arco (u,v) \in E tiene una capacidad no negativa  c(u,v) \ge 0.
Se distinguen dos vértices: la fuente s y el destino t.
Se supone que cada vértice se encuentra en alguna ruta de s a t.
Un flujo en G es una función f: V \times V \mapsto R tal que
  • Restricción de capacidad: \forall \quad u,v \in V,\quad f(u,v) \le c(u,v)
  • Simetría: f(u,v) = - f(v,u) \,
  • Conservación: \forall u \in V - \left \{ s,t \right \} \quad \sum_{v \in V} f(u,v) = 0
El valor del flujo es |f| = \sum_{v \in V}f(s,v)
El problema del flujo máximo trata de maximizar este flujo.
 

 

 

Algoritmo de Ford-Fulkerson

 
El algoritmo de Ford-Fulkerson propone buscar caminos en los que se pueda aumentar el flujo, hasta que se alcance el flujo máximo. Es aplicable a los Flujos maximales. La idea es encontrar una ruta de penetración con un flujo positivo neto que una los nodos origen y destino. Su nombre viene dado por sus creadores, L. R. Ford, Jr. y 
D. R. Fulkerson.

Sea (V,A,w) con V vértices, A aristas y w peso de las aristas, una red con una única fuente s y un único sumidero t; w(α) es la capacidad de α perteneciente a la arista A. Un flujo f es viable si f(α) <= w(α) para todo α perteneciente a la arista A. Se trata de hallar un flujo viable con el valor máximo posible.En un red con fuente s y sumidero t único el valor máximo que puede tomar un flujo variable es igual a la capacidad mínima que puede tomar un corte.

 

 

 

 

 

Esta pagina fue creada con la finalidad de  elaboracion de trabajos y aplicacion de nuestros conocimientos sobre la Teoría de grafos