Flujo máximo.

Al obtener una red, si se desea hallar su flujo máximo, lo que hay que hacer, es seleccionar un inicio, y un fin.

Por ejemplo para la siguiente red, tomaremos como inicio u origen el nodo 1, y como fin el nodo 5.

 

Al ubicarnos en el nodo 1, lo siguiente por hacer es realizar una etiquetarlo de forma [ ,--], y estando ubicados en este nodo, lo que haremos es escoger cual de las aristas es la que tiene el mayor valor e irnos por este, sabemos que se irá por la arista de valor 30, que se dirigirá al nodo 3, estando en el nodo 3, lo etiquetaremos de la siguiente manera, [valor de envió, de que nodo viene], es decir [30,1], posteriormente se buscara el flujo máximo que parte de 3, es decir 20, que se dirige a 5, estando en 5 se etiquetara de la misma forma, [20,3].

 

Ahora se declarara k_min,    cuyos valores serán los valores de los nodos por los que se viajo, es decir [30,10], el valor de menor  valor es el de 10, por lo tanto k_min será igual a 10.

Ahora recorriendo este camino, lo que haremos es lo siguiente;

C_ij, C_ji = [i-k , j+k]

Donde i sera el valor de salida en la arista, y j el valor de llegada de la misma.

Ahora aplicando esto en nuestra red.

C₁₃, C₃₁ = [30-10, 0+10]

C₃₅, C₅₃ = [20-10, 0+10]

De esta forma:

C₁₃, C₃₁ = [20, 10]

C₃₅, C₅₃ = [10, 10]

Se reemplazan estos valores en los nodos indicados, el primer numero sera la salida, y el Segundo la llegada.

Después de reemplazar los valores en la red.

Posteriormente haremos el mismo procedimiento de escoger desde el nodo de inicio, el valor máximo, y realizar su respectiva etiquetada.

 

Luego haremos el mismo procedimiento de

C_ij, C_ji = [i-k , j+k]

Y se hallara mos k_min

k_min = 5;

Haremos su respectiva etiquetada.

Esta es la red obtenida.

Ahora repetiremos este procedimiento hasta dejar las conexiones saturadas, el decir que su salida es de 0,

Para así finalmente después de obtenidas todas las k_min  realizar su sumatoria, para así obtener su flujo máximo.