4.3.6. Otros problemas con grafos.

Problemas de flujo en redes

• Supongamos un grafo dirigido G=(V, A) con pesos en las aristas. Los pesos de cada arista C(v, w) representa el número máximo de unidades que pueden “fluir” desde el nodo v al w.

• Por ejemplo: C(v, w) puede ser la cantidad máxima de agua que puede ir por una tubería que comunica v con w, o el número de coches máximo que cabe en una calle.

• Problema de flujo máximo.

Dado un nodo origen s y un nodo destino t en un grafo dirigido con pesos, encontrar la cantidad máxima de flujo que puede pasar de s a t.

s

t

a

c

b

d

2

3

3

4

1

2

3

2

s

t

a

c

b

d

2

3

2

1

0

2

3

2

• La suma de entradas para cada nodo interior debe ser igual a la suma de salidas.

• Los valores de flujo en cada arista no pueden superar los valores máximos.

Diapositiva anterior

Diapositiva siguiente

Ir a la primera diapositiva

Ver versión gráfica