flujo en redes de transportecb.mty.itesm.mx/tc1003/lecturas/tc1003-117.pdf · flujo en redes de...

Flujo en Redes de TransporteEduardo Uresti

Flujo en Redes de Transporte– p.1/55

Red de Transporte

Una Red de Transporte es un grafo dirigido con peso(V,E, c) donde hay dos vértices distinguidos: uno llamadofuente y otro llamado sumidero. Se asume que todo vérticedel grafo v ∈ V está en un camino s Ã v Ã t. El peso decada lado debe ser no negativo y se considera lacapacidad del lado. Si (u, v) /∈ E, c(u, v) = 0.

s

v1 v2

t

v3v4

16

13

1220

7

4

14

94 10


Un Flujo

Un flujo en una red de transporte (V,E, c) es una funciónf : V × V → < que satisface:


Un Flujo


1. Restricción de capacidad: ∀u, v ∈ V : f(u, v) ≤ c(u, v)


Un Flujo



2. Antisimetría: ∀u, v ∈ V : f(u, v) = −f(v, u)


Un Flujo




3. Conservación del flujo: ∀u ∈ V − {s, t}:∑

v∈V

f(u, v) = 0


Un Flujo





v∈V

f(u, v) = 0

f(u, v) se llamará el flujo de u a v.


Un Flujo





v∈V

f(u, v) = 0

f(u, v) se llamará el flujo de u a v. El valor del flujo f sedefine como:

|f | =∑

v∈V

f(s, v)


Ejemplo de Flujo

c s v1 v2 v3 v4 t

s 0 16 0 0 13 0

v1 0 0 12 0 10 0

v2 0 0 0 0 9 20

v3 0 0 7 0 0 4

v4 0 4 12 14 0 0

t 0 0 0 0 0 0

f s v1 v2 v3 v4 t

s 0 11 0 0 8 0

v1 -11 0 12 0 -1 0

v2 0 -12 0 -7 4 15

v3 0 0 7 0 -11 4

v4 -8 1 -4 11 0 0

t 0 0 -15 -4 0 0

s

v1 v2

t

v3v4

11/16

8/13

12/1215/20

7/7

4/4

11/14

4/91/4 10


Tarea 1:

Suponga una red de transporte (V,E, c) y un flujo en ella f .Si no hay lado de u a v ni de v a u entonces

f(u, v) = f(v, u) = 0


Red Residual

Sea G = (V,E, c) una red de transporte y f un flujo sobreella. La capacidad residual de lado (u, v) respecto a f sedefine como:

cf (u, v) = c(u, v) − f(u, v)


Capacidad Residual: Ejemplo

c s v1 v2 v3 v4 t

s 0 16 0 0 13 0

v1 0 0 12 0 10 0

v2 0 0 0 0 9 20

v3 0 0 7 0 0 4

v4 0 4 12 14 0 0

t 0 0 0 0 0 0

f s v1 v2 v3 v4 t

s 0 11 0 0 8 0

v1 -11 0 12 0 -1 0

v2 0 -12 0 -7 4 15

v3 0 0 7 0 -11 4

v4 -8 1 -4 11 0 0

t 0 0 -15 -4 0 0

cf s v1 v2 v3 v4 t

s 0 5 0 0 5 0

v1 11 0 0 0 11 0

v2 0 12 0 7 5 5

v3 0 0 0 0 11 0

v4 8 3 15 3 0 0

t 0 0 15 4 0 0


Red Residual

Dada una red de transporte G = (V,E, c) y un flujo f , la redresidual de G inducida por f , Gf = (V,Ef , cf ) donde

Ef ={

(u, v) ∈ V × V : cf (u, v) > 0}


Red Residual

cf (p) = mı́n{

cf (u, v) : (u, v) ∈ p}

cf s v1 v2 v3 v4 t

s 0 5 0 0 5 0

v1 11 0 0 0 11 0

v2 0 12 0 7 5 5

v3 0 0 0 0 11 0

v4 8 3 15 3 0 0

t 0 0 15 4 0 0

s

v1 v2

t

v3v4

5

115

8

125

157

43

11

5

43 11


Ejemplo

s

v1 v2

t

v3v4

11/16

8/13

12/1215/20

7/7

4/4

11/14

4/91/4 10

s

v1 v2

t

v3v4

5

115

8

125

157

43

11

5

43 11


Extensión def a pares de conjuntos

Sean X y Y subconjuntos de vértices:

f(X,Y ) =∑

x∈X

∑

y∈Y


Propiedades

Sea G = (V,E, c) una red de transporte y f un flujo sobre G:

f(X,X) = 0

f(X,Y ) = −f(Y,X)

Si X ∩ Y = ∅: f(X ∪ Y, Z) = f(X,Z) + f(Y, Z)


Resultado

Sea G = (V,E, c) una red de transporte con fuente t ysumidero t, y sea f un flujo en G. Sea Gf la red detransporte residual inducida por f , y además sea f ′ un flujoen Gf . Entonces si se define la función f + f ′ : V × V → <como

(f + f ′)(u, v) = f(u, v) + f ′(u, v)

entonces f + f ′ es un flujo sobre G con valor |f + f ′| =

|f | + |f ′|.


Caminos aumentados

Sea G = (V,E, c) una red de transporte y f un flujo. Uncamino aumentado es un camino simple de s a t en la redresidual Gf . Por definición, en cada lado (u, v) de uncamino residual es posible aumentar el flujo de (u, v) enuna cantidad positiva sin violar la restricción de lacapacidad en ese lado. La capacidad residual del caminoaumentado p se define como

cf (p) ={

cf (u, v) : (u, v) es un lado de p}


Lema

Sea G = (V,E, c) una red de transporte,f un flujo en G, p uncamino aumentado en Gf . Define la función:fp : V × V → < como

fp(u, v) =

cf (p) si (u, v) es un lado de p

−cf (p) si (v, u) es un lado de p

0 en otro caso.

Entonces, fp es un flujo en Gf con valor |fp| = cf (p) > 0.


Corolario

Sea G = (V,E, c) una red de transporte, f un flujo sobre G,

y p un camino aumentado sobre Gf . Si fp es el flujo definido

anteriormente, entonces f ′ = f +fp es un flujo sobre G cuyo

valor es |f ′| = |f | + |fp| > |f |.


Corte

Un corte (S, T ) de una red de transporte G = (V,E, c) esuna partición de V en dos conjuntos S y T = V − S tal ques ∈ S y t ∈ T . La capacidad de un corte (S, T ) es

c(S, T ) =∑

u∈S,v∈T

c(u, v)

s

v1 v2

t

v3v4

16

13

1220

7

4

14

94 10

c({s, v1, v4} , {v2, v3, t}) = 26


Ejemplo 2 de Corte

s

v1 v2

t

v3v4

16

13

1220

7

4

14

94 10

c({s, v1, v4} , {v2, v3, t}) = 16 + 4 + 7 + 4 = 31


Lema

Sea f un flujo en una red de transporte G con fuente s ysumedero t, y sea (S, T ) un corte cualquiera. Entonces, elflujo neto a través de corte (S, T ) es f(S, T ) = |f |.El flujo neto a través de un corte se define como

f(S, T ) =∑

u∈S,v∈T

f(u, v)


Ejemplo de flujo neto

s

v1 v2

t

v3v4

11/16

8/13

12/1215/20

7/7

4/4

11/14

4/91/4 10

f({s, v1, v4} , {v2, v3, t}) = f(v1, v2) + f(v4, v2) + f(v4, v3)

= 12 + (−4) + 11

= 19


Lema

Sea f un flujo sobre la red de transporte G = (V,E, c) confuente s y sumidero t, y sea (S, T ) un corte de G. Entonces,el flujo neto a través del corte (S, T ) es |f |.


Lema

Sea f un flujo sobre la red de transporte G = (V,E, c) confuente s y sumidero t, y sea (S, T ) un corte de G. Entonces,el flujo neto a través del corte (S, T ) es |f |.

Notando que f(S − s, V ) = 0 tenemos:

f(S, T ) = f(S, V ) − f(S, S)

= f(S, V )

= f(s, V ) + f(S − s, V )

= f(s, V )

= |f |


Lema

El valor de cualquier flujo en una red de transporte estáacotado superiormente por la capacidad de cualquier cortede G.


Lema

El valor de cualquier flujo en una red de transporte estáacotado superiormente por la capacidad de cualquier cortede G.

Sea (S, T ) un corte cualquiera de G y sea f cualquier flujo:por el lema anterior:

|f | = f(S, T )

=∑

u∈S,v∈T f(u, v)

=∑

u∈S

∑

v∈T f(u, v)

≤∑

u∈S

∑

v∈T c(u, v)

=∑

u∈S,v∈T c(u, v)

= c(S, T )


Teorema Fundamental

Sea f un flujo sobre la red de transporte G = (V,E, c) confuente s y sumidero t, entonces las siguientes condicionesson equivalentes:

1. f es un flujo máximo sobre G.

2. La red residual Gf no contiene caminos aumentados.

3. |f | = c(S, T ) para algún corte (S, T ) de G.


Demostración

(1) =>(2)

Por contradicción: suponga que Gf es máximo pero que Gf

posee un camino aumentado p. Por consiguiente, f + fp es

un flujo sobre G cuyo valor es |f + fp| > |f | por tanto f no es

máximo.


Demostración

(2) =>(3)Suponga que no existe un camino aumentado de s a t enGf . Defina

S = {v ∈ V : existe un camino de s a v}

y T = V − S. Así (S, T ) es un corte para G donde s ∈ S yt ∈ T y para cada par de vértices (u, v), u ∈ S y v ∈ T ,f(u, v) = c(u, v) porque de otra forma v ∈ S. Y

c(S, T ) =∑

u∈S,v∈T

c(u, v) =∑

u∈S,v∈T

f(u, v) = f(S, T ) = |f |


Demostración

(3) =>(1)Suponga que |f | = c(S, T ) para algún corte (S, T ) de G.Como |f | ≤ c(S, T ) para cualquier corte, entonces |f | esmáximo. Pues en caso contrario existiría otro flujo f ′ tal que

c(S, T ) = |f | < |f ′| ≤ c(S, T )


Ford-Fulkerson

1. para cada lado (u, v) ∈ E(G)hacer

f(u, v) = 0f(v, u) = 0

2. mientras no exista un camino p de s a t en Gf

hacer

cf (p) = mı́n{

cf (u, v) : (u, v) ∈ p}

para cada lado (u, v) ∈ phacer

f(u, v) = f(u, v) + cf (p)

f(v, u) = −f(u, v)


Ejemplo

s

v1 v2

t

v3v4

16

13

1220

7

4

14

94 10

s

v1 v2

t

v3v413

7

4

14

94 10

1612

20


Ejemplo

s

v1 v2

t

v3v413

7

4

14

94 10

1612

20

s

v1 v2

t

v3v413

7

4

14

94 10

12/1612/12

12/20


Ejemplo

s

v1 v2

t

v3v413

7

4

14

94 10

12/1612/12

12/20

s

v1 v2

t

v3v413

7

4

14

94 10

4

12

128

12


Ejemplo

s

v1 v2

t

v3v413

7

4

14

94 10

4

12

128

12

s

v1 v2

t

v3v413

79

412

128

1210

4

14

4


Ejemplo

s

v1 v2

t

v3v413

79

412

128

1210

4

14

4

s

v1 v2

t

v3v413

79

412

128

124/10

4/4

4/14

4/4


Ejemplo

s

v1 v2

t

v3v413

79

412

128

124/10

4/4

4/14

4/4

s

v1 v2

t

v3v413

79

816

128

126

10

44


Ejemplo

s

v1 v2

t

v3v4

9816

128

126

44

7

13 10

s

v1 v2

t

v3v4

9816

12

126

4413 10

7

8


Ejemplo

s

v1 v2

t

v3v4

9816

12

126

4413 10

7

8

s

v1 v2

t

v3v4

9816

12

126

447/13 7/10

7/7

7/8


Ejemplo

s

v1 v2

t

v3v4

9816

12

126

447/13 7/10

7/7

7/8

s

v1 v2

t

v3v4

9816

12

196

114

4

7 3

7

1


Ejemplo Negativo

s

u

v

t

1000

1000 1

1000

1000

s

u

v

t1000

10001000

1 1000


Ejemplo Negativo

s

u

v

t1000

10001000

1 1000

s

u

v

t

1000

10001/1000 1/1

1/1000


Ejemplo Negativo

s

u

v

t

1000

10001/1000 1/1

1/1000

s

u

v

t

1000

1000999

1

1

999

1


Ejemplo Negativo

s

u

v

t

1000

1000999

1

1

999

1

s

u

v

t999

1

999

1

1000

1 1000


Ejemplo Negativo

s

u

v

t999

1

999

1

1000

1 1000

s

u

v

t

1/1000

1/1000999

1

1/1

999

1


Ejemplo Negativo

s

u

v

t

1/1000

1/1000999

1

1/1

999

1

s

u

v

t999

1

999

1

999

11 999

1


Ejemplo Negativo

s

u

v

t999

1

999

1

999

11 999

1

s

u

v

t

1

1

999

1

1

999999 1

999


Ejemplo Negativo

s

u

v

t

1

1

999

1

1

999999 1

999

s

u

v

t

1

1

999

1

1

9991/999 1/1

1/999


Ejemplo Negativo

s

u

v

t

1

1

999

1

1

9991/999 1/1

1/999

s

u

v

t

2

2

999

1

1

999998 1

998


Ejemplo Negativo

s

u

v

t

2

2

999

1

1

999998 1

998

s

u

v

t

2

21

1

998

998

1

999

999


Edmonds-Karp

Estrategia para determinar un Camino Aumentado: Utilizarcamino más corto con longitud de cada lado igual con 1.El número total de caminos aumentados construidos por elalgoritmo es O(nm).

El tiempo total de ejecucción O(n2m).


Ejercicio

Para el grafo:

s

v1 v2

t

v3v4

105

83

108

6

2

1 103

Determine la capacidad del corte (S = {s, v3), V − S).


Ejercicio

Para la red y el flujo:

s

v1 v2

t

v3v4

2/102/5

2/83

1/101/8

6

2

1/1 103

Determine el flujo neto sobre el corte (S = {s, v3), V − S).


Ejercicio

Para la red y el flujo:

s

v1 v2

t

v3v4

2/102/5

2/83

1/101/8

6

2

1/1 103

Determine la red residual.


Ejercicio

Para el grafo y el camino:

s

v1 v2

t

v3v4

8

6

2

1 103

105

3

8 10

Determine la red residual.


Ejercicio

Para el grafo:

s

v1 v2

t

v3v4

105

83

108

6

2

1 103

Determine el flujo máximo.


Ejercicio

Indique cómo puede reducirse el problema de una red de

transporte con varias fuentes y varios resumideros al pro-

blema de una sola fuente y un solo resumidero.


Ejercicio

El grado de conectividad por lado de un grafo no dirigido es

el mínimo número de lados que deben ser removidos para

que el grafo resultante no sea conexo. Indique cómo puede

ser transformado el problema de determinación del grado de

conectividad por lado de un grafo en un problema de flujo

máximo. Ejemplos: si el grafo no es conexo, el grado es 0;

si el grafo es un árbol es 1.


Ejercicio

Un grafo se dice Bipartido si el conjunto de vértices V puede

dividirse en dos conjuntos V1 y V2 de manera que los lados

del grafo sólo van de V1 a V2. (No hay lados de un vértice en

V1 a otro vértice en V1 y similarmente para V2) El problema

del máximo apareamiento en un grafo bipartido G = (V1 ∪

V2, E) consiste en determinar el número máximo de lados

no conectados que se pueden tomar con un vértice en V1 y

otro vértice en V2.


flujo en redes de transportecb.mty.itesm.mx/tc1003/lecturas/tc1003-117.pdf · flujo en redes de...

Documents