redes

Flujo en Redes

79

1 2
3

5

4

15

30

20

25

50
45

10

25

40

55

s

t
a c

b

d

2

3

3

4

1
2

3

2

Flujoen Redes. Flujo máximo

E:\Pedro\PlanDocente\Grafos\REE\mapaRT_3.gif
E:\Pedro\PlanDocente\Grafos\REE\london_big.jpg

Flujo en Redes

80

Indice

.Introducción.
.Flujo en redes..El método de Ford Fulkerson. Flujo máximo.
.Redes residuales.
.Caminos aumentantes.
.Cortes en redes de flujos.
.Teorema de flujo-máximo mínimo-corte.
.El algoritmo de Ford Fulkerson.
Flujo en Redes

81

Introducción

.Los digrafos se pueden usar para representar
flujo en redes.
.Permiten modelar todo tipo de red, en
particular las de transporte y distribución:–flujo de fluídos en tuberías, piezas en una línea de
ensamblaje, corriente en circuitos eléctricos,
información en redes de comunicación, etc.


.Problema: Maximizar la cantidad de flujo
desdeun vértice fuente a otro sumidero, sin
superar las restricciones de capacidad.
–Método de Ford-Fulkerson para resolver el
problema de máximo flujo.





Flujo en Redes

82

Redesde flujo

.Digrafo G=(V, E)
.Los pesos de las aristas representan capacidad
(c(u, v)> 0). Si no hay aristas la capacidad es
cero.
.Vértices especiales:


fuente s, vértice sin aristasde entrada.

sumidero t, vértice sin aristas de salida.

.El grafo es conectado: Hay un camino entre s y t
por algún vértice intermedio del grafo.



Flujo en Redes

83

Redes deflujo

.Un flujo en G es una función real f : VxV . . que
satisface las siguientes propiedades:
–Restricción de capacidad: Para todo u, v . V, f (u, v) < c (u, v)
–Antisimetría: Para todo u,v . V, f (u, v) = .f (v, u)
–Conservación de flujo: Para todo u . V . {s, t }, = 0


.Valor del flujo: | f | = =


..
Vvvuf),(
..
Vvvsf),(..
Vvtvf),(
v1

v3

v2

v4

s...