Redes De Flujo

Fuente
a) Un vértice fijo, la fuente denotada por a, no tiene aristas
de entrada

la fuente es quien produce o inicia el traspaso de algún material o producto por los arcos, estos últimos, vistoscomo 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.
Fuentes: punto departida del flujo total de una red.

fuente, al que se le asocia un flujo positivo y otro llamado sumidero que tiene un flujo negativo

Sumidero
b) Un vértice fijo, el sumidero (o destino) denotada porz, no
tiene aristas de salida
 Sumideros: es el punto de llegada del flujo total de una red.

Flujo estable

Flujo Máximo
En otras palabras, el problema consiste en determinar la máxima capacidad deflujo que puede ingresar a través de la fuente y salir por el nodo de destino.
El procedimiento para obtener el flujo máximo de una red, consiste en seleccionar repetidas veces cualquier trayectoriade la fuente al destino y asignar el flujo máximo posible en esa trayectoria.

Teorema de Flujo Máximo:

Teorema: Sea C: n0, n1, … , nk un camino de F = n0 a S = nk en una red R. Sea f un flujo en Rcon valores f(i,j). Para las aristas orientadas en forma propia tenemos W(i,j) < f(i,j) y para las no orientadas en forma propia f(i,j) > 0.
Definimos f + (i,j) como:
f(i,j) para las aristasque no están en el camino. f(i,j) + M si la arista está orientada en forma propia. f(i,j) – M si la arista no está orientada en forma propia.
M = min { W(i,j) – f(i,j) si (i,j) está orientada en formapropia y si f(i,j) no está orientada en forma propia }
Entonces f+ es un flujo que f precisa en el valor M.

Siendo G una red de trasporte, un flujo máximo es un flujo con valor máximo.
_ Engeneral, habrá varias flujos con el mismo valor máximo.
_ La idea es sencilla: comenzar con cierto flujo inicial e incrementar de forma iterativa hasta que no pueda mejorarse más. El flujo resultante será...