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
Flujo en Redes de Transporte– p.2/55
Un Flujo
Un flujo en una red de transporte (V,E, c) es una funciónf : V × V → < que satisface:
Flujo en Redes de Transporte– p.3/55
Un Flujo
Un flujo en una red de transporte (V,E, c) es una funciónf : V × V → < que satisface:
1. Restricción de capacidad: ∀u, v ∈ V : f(u, v) ≤ c(u, v)
Flujo en Redes de Transporte– p.3/55
Un Flujo
Un flujo en una red de transporte (V,E, c) es una funciónf : V × V → < que satisface:
1. Restricción de capacidad: ∀u, v ∈ V : f(u, v) ≤ c(u, v)
2. Antisimetría: ∀u, v ∈ V : f(u, v) = −f(v, u)
Flujo en Redes de Transporte– p.3/55
Un Flujo
Un flujo en una red de transporte (V,E, c) es una funciónf : V × V → < que satisface:
1. Restricción de capacidad: ∀u, v ∈ V : f(u, v) ≤ c(u, v)
2. Antisimetría: ∀u, v ∈ V : f(u, v) = −f(v, u)
3. Conservación del flujo: ∀u ∈ V − {s, t}:∑
v∈V
f(u, v) = 0
Flujo en Redes de Transporte– p.3/55
Un Flujo
Un flujo en una red de transporte (V,E, c) es una funciónf : V × V → < que satisface:
1. Restricción de capacidad: ∀u, v ∈ V : f(u, v) ≤ c(u, v)
2. Antisimetría: ∀u, v ∈ V : f(u, v) = −f(v, u)
3. Conservación del flujo: ∀u ∈ V − {s, t}:∑
v∈V
f(u, v) = 0
f(u, v) se llamará el flujo de u a v.
Flujo en Redes de Transporte– p.3/55
Un Flujo
Un flujo en una red de transporte (V,E, c) es una funciónf : V × V → < que satisface:
1. Restricción de capacidad: ∀u, v ∈ V : f(u, v) ≤ c(u, v)
2. Antisimetría: ∀u, v ∈ V : f(u, v) = −f(v, u)
3. Conservación del flujo: ∀u ∈ V − {s, t}:∑
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)
Flujo en Redes de Transporte– p.3/55
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
Flujo en Redes de Transporte– p.4/55
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
Flujo en Redes de Transporte– p.5/55
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)
Flujo en Redes de Transporte– p.6/55
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
Flujo en Redes de Transporte– p.7/55
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}
Flujo en Redes de Transporte– p.8/55
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
Flujo en Redes de Transporte– p.9/55
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
Flujo en Redes de Transporte– p.10/55
Extensión def a pares de conjuntos
Sean X y Y subconjuntos de vértices:
f(X,Y ) =∑
x∈X
∑
y∈Y
Flujo en Redes de Transporte– p.11/55
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)
Flujo en Redes de Transporte– p.12/55
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 ′|.
Flujo en Redes de Transporte– p.13/55
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}
Flujo en Redes de Transporte– p.14/55
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.
Flujo en Redes de Transporte– p.15/55
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 |.
Flujo en Redes de Transporte– p.16/55
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
Flujo en Redes de Transporte– p.17/55
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
Flujo en Redes de Transporte– p.18/55
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)
Flujo en Redes de Transporte– p.19/55
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
Flujo en Redes de Transporte– p.20/55
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 |.
Flujo en Redes de Transporte– p.21/55
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 |
Flujo en Redes de Transporte– p.21/55
Lema
El valor de cualquier flujo en una red de transporte estáacotado superiormente por la capacidad de cualquier cortede G.
Flujo en Redes de Transporte– p.22/55
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 )
Flujo en Redes de Transporte– p.22/55
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.
Flujo en Redes de Transporte– p.23/55
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.
Flujo en Redes de Transporte– p.24/55
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 |
Flujo en Redes de Transporte– p.25/55
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 )
Flujo en Redes de Transporte– p.26/55
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)
Flujo en Redes de Transporte– p.27/55
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
Flujo en Redes de Transporte– p.28/55
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
Flujo en Redes de Transporte– p.29/55
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
Flujo en Redes de Transporte– p.30/55
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
Flujo en Redes de Transporte– p.31/55
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
Flujo en Redes de Transporte– p.32/55
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
Flujo en Redes de Transporte– p.33/55
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
Flujo en Redes de Transporte– p.34/55
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
Flujo en Redes de Transporte– p.35/55
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
Flujo en Redes de Transporte– p.36/55
Ejemplo Negativo
s
u
v
t
1000
1000 1
1000
1000
s
u
v
t1000
10001000
1 1000
Flujo en Redes de Transporte– p.37/55
Ejemplo Negativo
s
u
v
t1000
10001000
1 1000
s
u
v
t
1000
10001/1000 1/1
1/1000
Flujo en Redes de Transporte– p.38/55
Ejemplo Negativo
s
u
v
t
1000
10001/1000 1/1
1/1000
s
u
v
t
1000
1000999
1
1
999
1
Flujo en Redes de Transporte– p.39/55
Ejemplo Negativo
s
u
v
t
1000
1000999
1
1
999
1
s
u
v
t999
1
999
1
1000
1 1000
Flujo en Redes de Transporte– p.40/55
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
Flujo en Redes de Transporte– p.41/55
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
Flujo en Redes de Transporte– p.42/55
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
Flujo en Redes de Transporte– p.43/55
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
Flujo en Redes de Transporte– p.44/55
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
Flujo en Redes de Transporte– p.45/55
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
Flujo en Redes de Transporte– p.46/55
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).
Flujo en Redes de Transporte– p.47/55
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).
Flujo en Redes de Transporte– p.48/55
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).
Flujo en Redes de Transporte– p.49/55
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.
Flujo en Redes de Transporte– p.50/55
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.
Flujo en Redes de Transporte– p.51/55
Ejercicio
Para el grafo:
s
v1 v2
t
v3v4
105
83
108
6
2
1 103
Determine el flujo máximo.
Flujo en Redes de Transporte– p.52/55
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.
Flujo en Redes de Transporte– p.53/55
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.
Flujo en Redes de Transporte– p.54/55
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 Transporte– p.55/55
Top Related