Algoritmo de Ford-Fulkerson

Algoritmo de Ford-Fulkerson

El algoritmo de Ford-Fulkerson busca una ruta creciente en el gráfico residual. Satura este camino si existe, de lo contrario devuelve el caudal máximo. Más precisamente, el algoritmo establece un corte mínimo para verificar el criterio de optimalidad. Recuerde que el caudal es menor o igual al corte.

Para inicializar el algoritmo, es posible atribuir cualquier flujo en el gráfico siguiendo rutas simples (desde la fuente hasta el sumidero). En el siguiente diagrama, hemos tomado la ruta s-2-3-t para la inicialización.

Gráfico de desviación del algoritmo de Ford-Fulkerson
Después de la construcción del gráfico residual, se elige una ruta de sa t si hay una. De lo contrario, tenemos el caudal máximo. En el primer caso, el nuevo flujo se calcula de acuerdo con la ruta creciente elegida en el gráfico de desviación: sumamos el flujo de la ruta creciente al flujo existente si el arco correspondiente en el gráfico original está en la misma dirección que el de la gráfico de desviación, de lo contrario restamos el flujo El algoritmo se detiene cuando ya no hay una ruta creciente.

Es posible formar un corte utilizando el último gráfico de espacios. Aplicamos un camino de s, todos los vértices que se pueden atravesar están en el conjunto S, los demás en el conjunto T. De hecho, los arcos saturados por el flujo cortan el gráfico en dos subconjuntos y forman el valor del corte.

Gráfico de desviación del algoritmo de Ford-Fulkerson

Si desea aumentar el flujo cambiando el valor, deberá aumentar el flujo máximo que puede pasar a través de estos arcos.

Algoritmo Ford-Fulkerson paso a paso

Gráfico de desviación del algoritmo de Ford-Fulkerson

El flujo inicial es 0. Aquí el gráfico residual GF es una copia del gráfico G. Estamos buscando una ruta de sa t, por ejemplo s-2-5-t:

Gráfico de desviación del algoritmo de Ford-Fulkerson

El valor mínimo de la ruta es 8. Agregamos este flujo de 8 a la ruta en el gráfico G.

Gráfico de desviación del algoritmo de Ford-Fulkerson

Como recordatorio, el gráfico residual debe mostrar los arcos inversos (que representan los flujos). El gráfico residual de la nueva iteración es el siguiente:

Gráfico de desviación del algoritmo de Ford-Fulkerson

Aquí elegimos la ruta s-2-3-5-t, con 2 para el flujo de bloqueo. Cuando elegimos un arco inverso (representando así un flujo), el nuevo flujo en el gráfico G se reduce como se muestra en este nuevo gráfico G.

Gráfico de desviación del algoritmo de Ford-Fulkerson

Valor del flujo = 10. Etc…

Gráfico de desviación del algoritmo de Ford-Fulkerson
Gráfico de desviación del algoritmo de Ford-Fulkerson

Valor de flujo = 16

Gráfico de desviación del algoritmo de Ford-Fulkerson

Elección de arco inverso (3,2):

Gráfico de desviación del algoritmo de Ford-Fulkerson

Valor de flujo = 18.

Gráfico de desviación del algoritmo de Ford-Fulkerson
Gráfico de desviación del algoritmo de Ford-Fulkerson

Valor de flujo = 19.

Gráfico de desviación del algoritmo de Ford-Fulkerson

Ya no hay un camino de sa t, hemos encontrado un flujo máximo para este gráfico G.

Compartir, repartir
es_ESES
A los bloggers de %d les gusta esto: