Scribd
Cargar
118 vistas22 páginas

Algoritmo de Flujo Máximo

El algoritmo Ford-Fulkerson encuentra el flujo máximo en una red mediante la identificación repetida de caminos de aumento desde la fuente al sumidero. En cada iteración, se asigna flujo al camino de aumento con capacidad residual mínima. Este proceso se repite hasta que no quedan más caminos de aumento posibles.

Cargado por

Sergio David Paez Suarez
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd
118 vistas22 páginas

Algoritmo de Flujo Máximo

El algoritmo Ford-Fulkerson encuentra el flujo máximo en una red mediante la identificación repetida de caminos de aumento desde la fuente al sumidero. En cada iteración, se asigna flujo al camino de aumento con capacidad residual mínima. Este proceso se repite hasta que no quedan más caminos de aumento posibles.

Cargado por

Sergio David Paez Suarez
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd

Algoritmo Ford-Fulkerson

Sergio David Paez Suarez - 20191020167


Algoritmo que permite dar
solución al problema del
flujo maximo.
1.
Problema del
Flujo Maximo

3
La idea general es dado un sistema de
distribución de un determinado material, para
el cual se dispone una red de distribución, a
de determinarse la máxima cantidad de
material que puede enviarse simultaneamente
por dicha red.
Consideraciones

Red de flujo.

Capacidad de arco.

Fuente.

Sumidero.
Redes y Flujo

Red: Grafo conexo
dirigido con capacidad
en sus aristas.

Capacidad:Valor
numerico positivo
asociado a las aristas.
Redes y Flujo

Flujo: Valor numericos
de las aristas de una red.

0 ≤ flujo ≤ capacidad
Redes y Flujo

Fuente: Nudo inicial
desde el cual se ingresa
el material a la red.

Sumidero: Nodo o puno
terminal hacia el cual
debe llegar el flujo.
Recorridos aumentativos
Secuencia de aristas entre la fuente y el
sumidero, recorridas en sentido directo o
sentido contrario.
Formas de identifcar recorridos
aumentativos
Existen dos formas de encontrar un recorrido → a simple vista o
mediante un grafo auxiliar

Grafo Auxiliar → Se toman los vertices de la red y se toman una


serie de condiciones para las aristas.

Vacías: Mismo sentido.

Llenas: Sendito inverso.

Ni llenas ni vacías: Ambos sentidos.
2.
Definición del
algoritmo

11
(1) Se comienza asignando un flujo nulo a cada arista de la red.
(2) Se identificar la trayectoria de mayor aumento.
(3) Se encuentra el mínimo de las capacidades residuales de las aristas
sobre la trayectoria.
(4) Se disminuye la capacidad residual de cada arista en la trayectoria
de aumento.
(5) Se aumenta el flujo maximo.
(6) Se repite el proceso hasta no encontrar más caminos.
(7) Se devuelve el flujo maximo de la red.
Ejemplo
flujoMaximo = 0
4 0/5
0/10
0/6

0/4
S 3 t
0/2
0/9
0/10

2
s-2-t

4 0/5
0/10
0/6

0/4
S 3 t
0/2
0/9
0/10

2
min(9,10) = 9

4 0/5
0/10
0/6

0/4
S 3 t
0/2
9/9
9/10

flujoMaximo = 9
s-4-3-t

4 0/5
0/10
0/6

0/4
S 3 t
0/2
9/9
9/10

2
min(10,6,4) = 4

4 0/5
4/10
4/6

4/4
S 3 t
0/2
9/9
9/10

flujoMaximo = 13
s-4-t

4 0/5
4/10
4/6

4/4
S 3 t
0/2
9/9
9/10

2
min(6,5) = 5

4 5/5
10/10
4/6

4/4
S 3 t
0/2
9/9
9/10

flujoMaximo = 18
Grafo Auxiliar

4 5/5
10/10
4/6

4/4
S 3 t
0/2
9/9
9/10

flujoMaximo = 18
Muchas gracias por su
atención.

22

También podría gustarte