Flujos Maximos









  • Mas formalmente, tenemos un grafo dirigido G = (V; E), s y t vértices de G, típicamente con din(s)=0 y dout(t) = 0 y una función de capacidad o .
  • Un flujo en G es una función tal que para cada e ϵ E, f (e) ≤ c (e) y además, para v ϵ V \ {s, t}, (ley de conservación).
  • El Valor del flujo es , que al igual que . Lo que busca es el flujo de valor máximo.


Variantes


Algunas variantes del problema de flujo:

  • Flujo en redes con arcos no dirigidos
  • Flujo factible, máximo o mínimo con cotas inferiores y superiores
  • Capacidades en los vértices
  • Flujo máximo con costo mínimo o acotado:
El costo es proporcional al flujo transportado a través del arco (fácil)
El costo es fijo y se cobra por el uso del arco (difícil)
  • Múltiples orígenes y destinos

Aplicaciones

El problema de flujo máximo se puede usar para modelar problemas de:


  • Transporte de mercadería (logística)
  • Flujo de gases y líquidos por tuberías
  • Flujo de componentes o piezas en líneas de montaje
  • Flujo de corriente en redes eléctricas
  • Flujo de paquetes de información en redes de comunicaciones
  • Tráfico ferroviario, etc.