Matemática Computacional

Algoritmo de Ford-Fulkerson

MATEMÁTICA COMPUTACIONAL - MA475

1

Logro El alumno, al término de la unidad, será capaz de manejar los distintos tipos de aplicaciones concernientes a la teoría de grafos, así como saber utilizar los algoritmos que resuelven problemas de camino más corto y redes de transporte.

MATEMÁTICA COMPUTACIONAL - MA475

2

Contenido • Algoritmo de Ford-Fulkerson para los casos:  Origen y destino conocidos  Origen y destino ficticios

MATEMÁTICA COMPUTACIONAL - MA475

3

Introducción

El algoritmo de Ford-Fulkerson (1962) propone buscar caminos de aumento, hasta que se alcance el flujo máximo. Su nombre viene dado por sus creadores, L. R. Ford y D. R. Fulkerson.

MA475 MATEMÁTICA COMPUTACIONAL

4

Algoritmo de Ford-Fulkerson Paso 1. Dada una red N, definimos un flujo inicial f en N como f(e)=0 para cada e de E. Paso 2. Etiquetamos la fuente a con (−,∞). Paso 3. Todo vértice x adyacente a a, es etiquetado como sigue: a) Si c(a,x)-f(a,x)>0, definimos ∆(x)=c(a,x)-f(a,x) y etiquetamos el vértice x con (a+, ∆(x)). b) Si c(a,x)-f(a,x)=0, dejamos el vértice x sin etiquetar.

La etiqueta (a+, ∆(x)) indica que el flujo presente de a a x puede incrementarse mediante la cantidad ∆(x) unidades adicionales proporcionadas desde a. MATEMÁTICA COMPUTACIONAL - MA475

5

Paso 4. Mientras exista x(≠a)∈ V tal que x está etiquetado y exista una

arista (x,y) tal que y no esté etiquetado, etiquetamos el vértice y: a) Si c(x,y)-f(x,y)>0, definimos ∆(y)=mín{∆(x), c(x,y)-f(x,y)} y etiquetamos el vértice y con (x+, ∆(y)). b) Si c(a,x)-f(a,x)=0, dejamos el vértice y sin etiquetar. Paso 5. Mientras exista x ≠ a tal que x está etiquetado y exista una arista (y,x) tal que y no esté etiquetado, etiquetamos el vértice y: a) Si f(y,x)>0, etiquetamos y como (x-,∆(y)) donde ∆(y)=mín{∆(x), f(y,x)}. b) Si f(y,x)=0, dejamos el vértice y sin etiquetar.

MATEMÁTICA COMPUTACIONAL - MA475

6

La etiqueta (x-, ∆(y)) indica que al disminuir el flujo de y a x, el total del flujo que sale de y a los vértices etiquetados puede ser disminuido en ∆(y). Estas ∆(y) unidades pueden utilizarse entonces para aumentar el flujo total de y a los vértices no etiquetados.

MATEMÁTICA COMPUTACIONAL - MA475

7

Ejemplo ¿Cuál es flujo máximo en la siguiente red de flujos?

MATEMÁTICA COMPUTACIONAL - MA475

8

Primero asociamos un flujo inicial nulo a cada arco y etiquetamos al nodo a:

MATEMÁTICA COMPUTACIONAL - MA475

9

Etiquetamos todo vértice adyacente a la fuente a (b y s). Luego, etiquetamos el vértice d (adyacente a b) y e (adyacente a s) :

MATEMÁTICA COMPUTACIONAL - MA475

10

Etiquetamos g (a partir de d), h (a partir de e) y z (a partir de h)

MATEMÁTICA COMPUTACIONAL - MA475

11

La variación del flujo en Z es ∆Z = 2, por tanto la red de flujos es:

MATEMÁTICA COMPUTACIONAL - MA475

12

Etiquetamos nuevamente mientras podamos encontrar caminos de a hasta z.

MATEMÁTICA COMPUTACIONAL - MA475

13

MATEMÁTICA COMPUTACIONAL - MA475

14

La última red de flujo corresponde a la de flujo máximo (ya no hay caminos posibles de a hasta z).

MATEMÁTICA COMPUTACIONAL - MA475

15

Desarrollemos juntos el algoritmo de Ford-Fulkerson

MATEMÁTICA COMPUTACIONAL - MA475

16

MATEMÁTICA COMPUTACIONAL - MA475

17

ORIGEN Y DESTINO FICTICIOS Si hay múltiples fuentes y sumideros, el problema se puede reducir al caso simple previo de una fuente y un destino. Supongamos que se tiene {s1, s2,…, sm} fábricas y {t1, t2,…, tn} puntos de venta, entonces la red de flujo a considerar es: S1  

s

t1 S2

t2



:



S3

:

 

t 

tn Sm MA475 MATEMÁTICA COMPUTACIONAL

18

Ejemplo Determine el flujo máximo de la siguiente red de flujos:

MA475 MATEMÁTICA COMPUTACIONAL

19