Flujo M Ximo Resumen Autoguardado

Flujo Máximo

Existe un flujo que viaja desde un único lugar de origen hacia un único lugar de destino a través de arcos que conectan nodos intermediarios. Los arcos tienen una capacidad máxima deflujo y se trata de enviar desde la fuente al destina la mayor cantidad posible de flujo.
Definiciones básicas

Flujo: Circulación de unidades homogéneas de un lugar a otro.

Capacidad de flujo: es lacapacidad de unidades que pueden entrar por el nodo fuente y salir por el nodo destino.

Origen o fuente de flujo: nodo por el cual el flujo ingresa.

Destino o Sumidero de flujo: nodo por el cual elflujo sale.

Capacidades residuales: Capacidades restantes unas vez que el flujo pasa el arco.



Algoritmo de flujo máximo
El algoritmo de flujo máximo se basa en determinar rutas de irrupción quetengan flujo neto positivo entre los nodos fuente y sumidero. Cada ruta comunica parte o todas las capacidades de sus arcos al flujo total en la red.
Paso 1. Para todos los arcos (i, j) se iguala lacapacidad residual con la capacidad inicial; esto es, (cij, cji) = (Cij, Cji). Sea a1= y se etiqueta el nodo fuente 1 con [ ,-]. Se iguala i=1 y se prosigue en el paso 2.
Paso 2. Determinar Si, elconjunto de nodos j no etiquetados que se pueden alcanzar directamente desde el noto i, con arcos residuales positivos (esto es, cij>0 para toda j ∈ Si). Si Si no está vacío se va al paso 3. En casocontrario ir al paso 4.
Paso 3. Determinar k ∈ Si tal que

Igualar ak= cik y etiquetar el nodo k con [ak, i]. Si k=n, el nodo de sumidero se ha etiquetado, y se ha encontrado una ruta de irrupción, iral paso 5. En caso contrario, igualar i=k y seguir en el paso 2.

Paso 4. (Retroceso). Si i = 1, no hay otras irrupciones posibles; ir al paso 6. En caso contrario, ser r el nodo que se ha etiquetadoinmediatamente antes del nodo actual i y quitar i del conjunto de nodos adyacentes a r. igualar i = r y continuar en el paso 2.
Paso 5. (Determinación de la red residual). Sea Np = ( 1, k1, k2, k3,...