• Author / Uploaded
• AMYNNXXXX

Citation preview

22 – Laboratorio de Matem´aticas : Teor´ıa de Grafos

1.5

1.5 Redes. Flujo m´aximo

Redes. Flujo m´ aximo

Otro de los grandes problemas de optimizaci´on se da en la b´ usqueda del flujo m´aximo en las redes de distribuci´on. Definici´ on 33.- Llamaremos red a un digrafo simple con dos v´ertices especiales, un minimal (la fuente) s y un maximal (el pozo) t, y que tiene asignada una capacidad no negativa cij a cada arco (vi , vj ) del digrafo. Un flujo f , es una asignaci´on de un valor fij a cada arco (vi , vj ) del digrafo. Escribiremos f+ (v) para denotar el flujo total saliente de un v´ertice v ; y f− (v) para denotar el flujo total entrante. Es decir P P f+ (vi ) = fik , la suma de los flujos de los arcos salientes de vi y f− (vi ) = fki , la suma de los flujos k

k

de los arcos entrantes. El flujo debe cumplir dos condiciones (en ocasiones se distingue denomin´andolo flujo factible o v´alido): • el flujo en cada arco debe ser no negativo y no exceder la capacidad del arco, 0 ≤ fij ≤ cij • en cada v´ertice v 6= s y v 6= t, distinto de la fuente y el pozo, debe cumplirse que f− (v) = f+ (v) (“Conservaci´ on del flujo” o “Ley de Kirchhoff”) Naturalmente es obvio que f− (s) = 0 = f+ (t). Y es sencillo comprobar que

om

Lema 34.- Para cualquier flujo (factible) en una red se cumple que f+ (s) = f− (t)

a1

.c

Demostraci´on: P P En efecto, por ser un digrafo (todo arco sale de un v´ertice y llega a otro) se tiene f− (v) = f+ (v), v∈V

v∈V

at

ic

y como por la ley de Kirchhoff, f− (v) = f+ (v) para todo v que no sea s ni t, la igualdad se reduce a f− (s) + f− (t) = f+ (s) + f+ (t), pero como f− (s) = f+ (t) = 0, se tiene que f+ (s) = f− (t).

em

A ese valor com´ un del flujo saliente en s y del flujo entrante en t se le llama valor del flujo, es decir, val(f ) = f+ (s) = f− (t).

1.5.1

ww

w.

M

at

Reconoceremos m´as f´acilmente ahora que los flujos en redes son de aplicaci´on en multitud de campos, en redes de flujo el´ectrico, distribuci´on de agua, tr´afico en carreteras, redes de transmisi´on de datos, distribuci´on de mercancias del productor al consumidor, etc. El objetivo de la optimizaci´on es por tanto maximizar el valor del flujo en la red. Y la manera de hacerlo es buscar caminos desde el nodo fuente al pozo en los que sea posible aumentar el flujo.

Recorridos aumentadores

Antes de nada, intentemos explicar c´omo puede aumentarse el flujo, ejemplificando sobre los dibujos siguientes. Sobre cada arco indicamos su capacidad y el flujo actual entre par´entesis y para indiciar los datos, suponemos s = v0 y t = v5 . Supongamos que tenemos un camino de s a t, un camino legal siguiendo las direcciones de las flechas, tal que en cada arco del camino el flujo existente no ocupa toda la capacidad del arco, que hay margen en cada arco para aumentar el flujo (como s = v0 →v1 →v2 →v5 = t en el dibujo, con c01 − f01 = 2 − 1 = 1 > 0, c12 − f12 = 3 − 1 = 2 > 0 y c25 − f25 = 2 − 0 = 2 > 0). Entonces, si sumamos el m´ınimo de los m´argenes m al flujo de cada arco del camino, el nuevo flujo f 0 as´ı construido es v´alido y 0 = 1 + 1, tiene mayor valor, val(f 0 ) = val(f ) + m > val(f ) (en nuestro ejemplo 1 = m´ın{1, 2, 2}, y f01 0 0 0 f12 = 1 + 1, f25 = 0 + 1, con val(f ) = val(f ) + m = 1 + 1). m12 = 1

f

vs1 (1)3 -vs2 m25 = 2 H © * (1)2 ©© ¡ HH(0) 2 HH ¡ ©© (1)1 ¡ H j st sH s © * ©© H ¡ © HH © ¡ (0)1 HH ª j s¡ - s©© (1) 1 v3 (1)1 v4 m01 = 1

Prof: Jos´ e Antonio Abia Vian

vs1 (1+1) 3 -vs2 H © * (1+1) 2 ©© ¡ HH(0+1) 2 © HH ¡ © (1) 1 ¡ H j st sH s © * ©© H ¡ © HH © ¡ (0)1 HH ª j s¡ - s©© (1)1 v3 (1)1 v4

f0

I.T.I. en Electricidad

23 – Laboratorio de Matem´aticas : Teor´ıa de Grafos

1.5 Redes. Flujo m´aximo

El camino de s a t que hemos tomado ser´a por tanto un camino aumentador del flujo. Pero puede ocurrir que no dispongamos de estos caminos y sin embargo el flujo pueda aumentarse. Con el nuevo flujo obtenido sobre la red no podemos encontrar otro camino aumentador, pues no podemos aumentar yendo desde s por v1 , y tampoco con el camino s → v3 → v4 . Existe otra posibilidad, que es considerar “recorridos” sin tener en cuenta el sentido de las flechas (que ser´an “caminos” no legales, pero v´alidos para nuestros propositos): supongamos que tenemos un “recorrido” de s a t, sin tener encuenta las direcciones de las flechas, tal que cada arco de ese camino siguiendo la direcci´on de las flechas (hacia adelante) el flujo existente no ocupa toda la capacidad del arco –que hay margen para aumentar el flujo–, y que en cada arco del camino en direcci´on contraria de la flecha (hacia atr´as) el flujo existente es mayor que cero –que hay margen para disminuir el flujo– (como s = v0 →v3 ←v2 →v5 = t en el dibujo, con c03 − f03 = 1 − 0 = 1 > 0, f23 = 1 > 0 y c25 − f25 = 2 − 1 = 1 > 0). Entonces, si sumamos el m´ınimo de los m´argenes m al flujo de cada arco hacia adelante y se lo restamos al flujo de cada arco hacia atr´as, el nuevo flujo f 0 as´ı construido es v´alido y 0 = 0+1, f 0 = 1−1, tiene mayor valor, val(f 0 ) = val(f )+m (en nuestro ejemplo 1 = m´ın{1, 1, 1}, y f03 23 0 = 1 + 1, con val(f 0 ) = val(f ) + m = 2 + 1 = 3). f25 vs1 (2)3 -vs2 © * (2)2 ©© ¡HHH(1+1) 2 © H ¡ © HH (1−1) 1 ¡ j st s© s H © * © HH ¡ © © ¡ (0+1) 1 HHH ª j s¡ - s©© (1)1 v3 (1)1 v4

f0

.c

om

vs1 (2)3 -vs2 m25 = 1 © * (2)2 ©© ¡HH (1) 2 HH ¡ ©© HH (1)1 js s© ¡ s H © * t m = 1 © 23 HH ¡ © © ¡ (0)1 HHH ª j s¡ - s©© (1) 1 v3 (1)1 v4 m03 = 1

a1

f

em

at

ic

El “recorrido” de s a t es por tanto un recorrido aumentador, y en este sentido se definen los recorridos (tambi´en llamados caminos) aumentadores. Todo recorrido aumentador debe comenzar en s y acabar en t, tener un margen m´ınimo positivo (sino no ser´a aumentador) y no pueden repetirse v´ertices (sin direcciones, un camino no dirigido).

M

at

Lema 35.- Si P es un recorrido aumentador con margen m´ınimo m, entonces incrementando el flujo en m en los arcos hacia adelante de P y reduciendo el flujo en m en los arcos hacia atr´as de P se obtiene un flujo v´alido con val(f 0 ) = val(f ) + m.

ww

w.

Demostraci´on: P es un recorrido de s a t, como s es minimal y t maximal, el arco de s al primer v´ertice y el arco del u ´ltimo v´ertice a t son hacia adelante, por lo que para el nuevo flujo se suma en ambos m (+). En los v´ertices intermedios solo pueden darse 4 situaciones (como en el dibujo): (i) vi est´a entre dos arcos hacia adelante, en ambos se suma m (+ y +); (ii) vj est´a entre un arco hacia adelante y otro hacia atr´as, en el primero se suma m y en el segundo se resta m (+ y −); (iii) vk est´a entre un arco hacia atr´as y otro hacia adelante, se resta m y se suma m (− y +); (iv) vs est´a entre dos arcos hacia atr´as, en ambos se resta m (− y −). +

+

+

+

−

−

+

−

−

+

s →v1 · · · vi−1 → vi →vi+1 · · · vj−1 → vj ←vj+1 · · · vk−1 ← vk →vk+1 · · · vs−1 ← vs ←vs+1 · · · vn → t (i) el arco anterior a vi incrementa su flujo en m, luego f−0 (vi ) = f− (vi )+m (los dem´as arcos entrantes en vi no modifican su flujo), y el arco siguiente saliente de vi tambi´en incrementa su flujo en m, luego f+0 (vi ) = f+ (vi ) + m (los dem´as arcos salientes de vi no modifican su flujo); por lo que se mantiene la condici´on del flujo f−0 (vi ) = f+0 (vi ) para el v´ertice. (ii) el arco anterior a vj , que es hacia adelante y entrante en vj , incrementa su flujo en m y el arco siguiente tambi´en es entrante en vj , pero es hacia atr´as, por lo que reduce su flujo en m, luego f−0 (vj ) = f− (vj ) + m − m = f− (vj ) y como los salientes de vj no aparecen invlolucrados, tambi´en se mantiene f+0 (vj ) = f+ (vj ); por lo que f−0 (vj ) = f+0 (vj ) para el v´ertice. Prof: Jos´ e Antonio Abia Vian

I.T.I. en Electricidad

24 – Laboratorio de Matem´aticas : Teor´ıa de Grafos

1.5 Redes. Flujo m´aximo

(iii) Es an´alogo al caso (ii) con ambos arcos salientes del v´ertice: f+0 (vk ) = f+ (vk ) − m + m = f+ (vk ) (iv) An´alogo al caso (i) con ambos arcos hacia atr´as f−0 (vs ) = f− (vs ) − m y f+0 (vs ) = f+ (vs ) − m luego todos los v´ertices distintos del fuente y el pozo verifican la condici´on de flujo. Adem´as, es evidente que al tomar como m el m´ınimo de los m´argenes de holgura hasta la capacidad en los v´ertices hacia adelante, no superaremos la capacidad de esos arcos al aumentar el flujo con m y, como este valor es tambi´en el m´ınimo de los flujos de arco en los arcos hacia atr´as, el flujo de estos arcos seguir´a siendo no negativo al restar m. Luego tambi´en 0 ≤ fij0 ≤ cij en cada arco. Finalmente, como f+0 (s) = f+ (s)+m y f−0 (t) = f− (t)+m el valor del nuevo flujo estar´a incrementado en m, es decir, val(f 0 ) = val(f ) + m.

1.5.2

Conjuntos de corte

a1

.c

om

Definici´ on 36.- Si dividimos el conjunto de v´ertices de la red en dos conjuntos, S conteniendo a s y T conteniendo a t, se llama conjunto de corte y se denota por [S, T ], a los arcos que unen nodos de S y T. Se llama capacidad del conjunto de corte a la suma de las capacidades de los arcos “hacia adelante” (que van de un v´ertice de S a un v´ertice de T ) y se dice que el flujo neto a trav´es del conjunto de corte es la suma de los flujos de los arcos “hacia adelante” menos los flujos de los arcos “hacia atr´as” (que van de un v´ertice de T a un v´ertice de S ).

at

em

at

ic

Usando la notaci´on ya introducida de flujo saliente y entrante, el flujo neto a trav´es del conjunto de corte lo podemos representar por f+ (S) − f− (S), el flujo saliente de S (de los arcos “hacia adelante”) menos el flujo entrante en S (de los arcos “hacia atr´as”). Aunque el conjunto de corte est´e formado por los arcos, es la elecci´on de los conjuntos S y T quien lo determina. De hecho, se les denomina de conjuntos de corte porque si eliminamos esos arcos se desconecta el digrafo, pero no cualquier conjunto de arcos que desconecte el digrafo es un conjunto de corte. La u ´nica regla que debe cumplirse para la divisi´on de los nodos en los conjuntos S y T es que s ∈ S y t ∈ T .

[S1 , T1 ]

ww

w.

M

Ejemplo En la red que hemos usado antes, los conjuntos de corte [S1 , T1 ], con S1 = {s, v1 , v3 } y T1 = {v2 , v4 , t} (a la izquierda en el dibujo), y [S2 , T2 ], con S2 = {s, v2 , v3 } y T2 = {v1 , v4 , t} (la figura de la derecha): (2) 3

-vs2 ¡HH (1)2 (2)2 © H © ¡ HH © (1)1 H j st s © ¡ s H * ©© HH ¡ © © ¡ (0)1 HHH ª j s¡ -© s © (1)1 v3 (1) 1 v4 vs1 * ©©

[S2 , T2 ] vs1 (2)3 -vs2 H © * (2)2 ©© ¡ HH(1)2 © HH ¡ (1)1 ¡ H js ©© s sH * t ©© HH ¡ © © ¡ (0)1 HHH ª j s¡ - s©© (1)1 v3 (1)1 v4

El conjunto de corte [S1 , T1 ] est´a formado por los arcos “hacia adelante” (v1 , v2 ) y (v3 , v4 ), y el arco “hacia atr´as” (v2 , v3 ); su capacidad ser´a cap [S1 , T1 ] = c12 + c34 = 3 + 1 y el flujo a trav´es de el, f+ (S1 ) − f− (S1 ) = (f12 + f34 ) − (f23 ) = 2 + 1 − 1 = 2. El segundo conjunto de corte [S2 , T2 ] est´a formado por los arcos “hacia adelante” (s, v1 ), (v3 , v4 ) y (v2 , t), y el arco “hacia atr´as” (v1 , v2 ); su capacidad ser´a cap [S2 , T2 ] = c01 + c34 + c25 = 2 + 2 + 1 y el flujo a trav´es de el, f+ (S2 ) − f− (S2 ) = (f01 + f34 + f25 ) − (f12 ) = 2 + 1 + 1 − 2 = 2. 4 Obs´ervese que en los dos casos del ejemplo anterior, las capacidades de los conjuntos de corte son diferentes, sin embargo el flujo neto a trav´es de ellos coincide; y, no por casualidad, coincide con val(f ). Lema 37.- Si U es un conjunto de v´ertices de una red, f+ (U ) − f− (U ) =

Prof: Jos´ e Antonio Abia Vian

P v∈U

f+ (v) − f− (v)

I.T.I. en Electricidad

25 – Laboratorio de Matem´aticas : Teor´ıa de Grafos

1.5 Redes. Flujo m´aximo

Demostraci´on: En efecto, veamos como contribuye cada arco de la red a los dos miembros de esta igualdad. Sea (vi , vj ) un arco del digrafo, entonces: ? si vi , vj ∈ / U , el arco no contribuye en ninguno de los dos miembros ? si vi , vj ∈ U , el arco no contribuye al primer miembro de la igualdad (ni es flujo saliente ni entrante en U ) y en el segundo miembro, contribuye con fij a f+ (vi ) (que suma) y con fij a f− (vj ) (que resta), por lo que contribuye en total con 0 ? si vi ∈ U y vj ∈ / U , fij contribuye a f+ (U ) del primer miembro y con fij a f+ (vi ) en el segundo miembro ? si vi ∈ / U y vj ∈ U , fij contribuye a f− (U ) del primer miembro y con fij a f− (vj ) en el segundo miembro Como la aportaci´ on de cada arco del digrafo es la misma en ambos t´erminos, la igualdad se cumple. Es muy sencillo ahora probar el interesante resultado siguiente

om

Lema 38.- El flujo neto a trav´es de cualquier conjunto de corte coincide con val(f )

a1

.c

Demostraci´on: P Por el lema anterior, el flujo neto a trav´es del conjunto de corte es f+ (S) − f− (S) = f+ (v) − f− (v). v∈S

at

ic

Como por la ley de conservaci´on del flujo f+ (v) = f− (v) para todo v 6= s, t y t ∈ / S , la suma se reduce a f+ (S) − f− (S) = f+ (s) − f− (s) = f+ (s) = val(f )

em

Corolario 39.- El valor del flujo de una red no puede exceder la capacidad de ning´ un conjunto de corte

M

at

Demostraci´on: val(f ) = f+ (S) − f− (S) ≤ f+ (S) que es la suma de los flujos de los arcos “hacia adelante” y como la capacidad del conjunto de corte es la suma de las capacidades de esos arcos y se cumple 0 ≤ fij ≤ cij , tenemos el resultado propuesto val(f ) ≤ f+ (S) ≤ cap [S, T ].

ww

w.

Con el resultado anterior podemos establecer el teorema que nos permitir´a la creaci´on de un algoritmo eficaz para la obtenci´on del flujo m´aximo: Teorema 40.- El valor del flujo de una red es m´aximo si y s´olo si no existe ning´ un recorrido aumentador Demostraci´on: Evidentemente, si existe un recorrido aumentador de s a t, el flujo puede aumentarse, por lo que no ser´ıa m´aximo. En el otro caso, si no existe un recorrido aumentador de s a t, veamos que el flujo es m´aximo. No existe un recorrido aumentador de s a t, pero podr´ıan construirse recorridos aumentadores a otros v´ertices de la red; sea entonces S0 el conjunto formado por s y los nodos a los que s´ı hay un recorrido aumentador, y T0 el resto. Como no hay recorrido aumentador de s a t, t ∈ T0 , luego [S0 , T0 ] es un conjunto de corte. Sea (vi , vj ) un arco cualquiera del conjunto de corte, entonces: ∗

• si vi ∈ S0 y vj ∈ T0 , debe ser fij = cij , pues como hay un recorrido aumentador de s a vi , s → vi , ∗ ∗ si fuera fij < cij tendr´ıamos un recorrido aumentador s → vi → vj , lo que no puede ser ya que vj ∈ T0 y no hay recorrido aumentador de s a vj . Luego fij = cij . ∗

• si vj ∈ S0 y vi ∈ T0 , debe ser fij = 0, pues como hay un recorrido aumentador de s a vj , s → vj , ∗ ∗ si fuera fij > 0 tendr´ıamos un recorrido aumentador s → vj ← vi , lo que no puede ser ya que vi ∈ T0 y no hay recorrido aumentador de s a vi . Luego fij = 0.

Prof: Jos´ e Antonio Abia Vian

I.T.I. en Electricidad

26 – Laboratorio de Matem´aticas : Teor´ıa de Grafos

1.5 Redes. Flujo m´aximo

En consecuencia, el flujo en los arcos “hacia adelante” coincide con la capacidad y en los arcos “hacia atr´as” es 0; por lo que val(f ) = f+ (S0 ) − f− (S0 ) = f+ (S0 ) = cap [S0 , T0 ]. Ahora bien, como val(f ) ≤ cap [S, T ] para cualquier conjunto de corte, en particular para [S0 , T0 ] y en ´el se da la igualdad, el flujo no puede aumentarse m´as por lo que es m´aximo. Teorema del flujo m´ aximo y corte m´ınimo (Ford-Fulkerson) 41.- El flujo m´aximo en una red es igual al m´ınimo de las capacidades de los conjuntos de corte Demostraci´on: De la demostraci´on del teorema anterior, si f es un flujo m´aximo su valor val(f ) = cap [S0 , T0 ] para un cierto conjunto de corte, pero como val(f ) ≤ cap [S, T ] para cualquier conjunto de corte, cap [S0 , T0 ] = val(f ) ≤ cap [S, T ] para cualquier conjunto de corte, y en consecuencia, [S0 , T0 ] es un conjunto de corte de capacidad m´ınima.

1.5.3

Algoritmo de Ford-Fulkerson o del Flujo m´ aximo

at

em

at

ic

a1

.c

om

Si bien el teorema del Flujo m´axino y corte m´ınimo es el m´as conocido y admirado, no es u ´til para la n−2 obtenci´on de un flujo m´aximo (en una red de n nodos tendr´ıamos que chequear 2 conjuntos de corte y eso s´olo para conocer el valor del flujo m´aximo). El algoritmo se basa en el Teorema 40 anterior, se van buscando recorridos aumentadores del flujo hasta que no sea posible encontrar m´as. Para la b´ usqueda del recorrido aumentador, se usan dos procesos que conviene explicar, el etiquetado de un v´ertice y la exploraci´ on de un v´ertice. Explorar un v´ertice es buscar los v´ertices conectados con ´el mediante un arco, saliente o entrante, y son estos v´ertices encontrados en la exploraci´ on los que son etiquetados; s´olo se etiquetan si no lo estaban ya y si tienen margen para aumentar el flujo. En el etiquetado, debe indicarse el v´ertice desde el que ha sido etiquetado y el margen posible de aumento; tambi´en suele indicarse si el arco para llegar a ´el se recorre “hacia adelante” o “hacia atr´as”. Inicialmente, se etiqueta solo s y se explora s, lo que produce el etiquetado de nuevos v´ertices. Para garantizar que la b´ usqueda avanza hacia t, se van explorando v´ertices ya etiquetados previamente –es decir para los que ya tenemos un recorrido aumentador– y no explorados, y se sigue as´ı hasta llegar a t.

M

Algoritmo 5.- (de Ford-Fulkerson)

w.

P.1.- Se etiqueta s con (0, ∞). (Es decir, no proviene de ning´un v´ertice y el margen es total.)

ww

P.2.- Si todos los v´ertices etiquetados han sido explorados, FIN (no hay recorrido aumentador) P.3.- Se busca un v´ertice etiquetado vi que no haya sido explorado P.4.- Si todo v´ertice adyacente a vi est´a etiquetado o no tiene “holgura”, se marca vi como explorado y se vuelve al Paso 2 P.5.- Para todo v´ertice adyacente vj no etiquetado, • Si el arco es (vi , vj ) “hacia adelante” y fij < cij , se calcula mj = m´ın{mi , cij − fij } (el margen m´ınimo acumulado) y se etiqueta vj con (i+ , mj ) • Si el arco es (vj , vi ) “hacia atr´as” y fji > 0, se calcula mj = m´ın{mi , fji } y se etiqueta vj con (i− , mj ) P.6.- Si t no est´a etiquetado, se vuelve al Paso 2 P.7.- Si t est´a etiquetado, hemos construido un recorrido aumentador R. Recorrer hacia atr´as el recorrido R aumentando el flujo existente con mt P.8.- Eliminar todas las etiquetas y volver al Paso 1.

Prof: Jos´ e Antonio Abia Vian

I.T.I. en Electricidad

27 – Laboratorio de Matem´aticas : Teor´ıa de Grafos

1.5 Redes. Flujo m´aximo

Como puede verse en la estructura, el algoritmo trata u ´nicamente de construir un recorrido aumentador y cuando lo encuentra, vuelve a empezar para construir otro; y as´ı hasta que no sean posibles m´as recorridos aumentadores. Notemos que cada v´ertice etiquetado es final de un recorrido aumentador “parcial” desde s, luego en el proceso se van obteniendo multiples recorridos aumentadores “parciales”, de hecho todos los posibles recorridos aumentadores hasta ese momento, y es s´olo la elecci´on del v´ertice a explorar la que determina que avancemos antes por un camino u otro. As´ı, cuando en la exploraci´ on de un v´ertice se dice que nos limitemos a los nodos no etiquetados (¡y con “holgura” claro!), no se est´an cercenando posibilidades (a ese v´ertice que no puedo etiquetar por que ya lo estaba, ya le llega un camino aumentador) y es la manera de garantizar que el recorrido aumentador a construir avanza hacia el pozo y no retrocede (y no se producen ciclos). S´olo as´ı se puede garantizar que el algoritmo termina y con ´exito. Veamos la aplicaci´on del algoritmo sobre la red usada anteriormente, haciendo v1 = s y v6 = t:

(1) 1

v5

(1+ , 1)(1) 1

Explorables = { v1 }

v5

r

(1+ , 1)(1) 1

v2 (2) 3 v3 r -H r © * (1) 2 © HH ¡ © (1) 1 H j r v6 r © ¡ HH © * © ¡ © (0) 1 HH (1) 1 ª j r¡ - r©

3 r (1 + 1) -r H (0 + 1) 2 ¡ HH (1) 1 ¡ H jr rH © © * © HH ¡ © (1) 1 (0) 1 ª j r¡ H -r © v

* © ©©

(1 + 1) 2

(1) 1

5

M

v5

Explorables = { v1 }

w.

(1) 1

ww

v4

−

v2 (2) 3 v3 -H r r © * (1) 2 © HH ¡ © (1) 1 H j r v6 rH © ¡ © * © H ¡ © (0) 1 HH (1) 1 ª j r¡ -r©

v2 (2) 3 (4 , 1) -H r r © * (1) 2 © HH ¡ © (1) 1 H j r v6 rH © ¡ © * © H ¡ © (0) 1 HH (1) 1 ª j r¡ -r©

(2) 2

(1+ , 1)(1) 1

(2) 2

v5

(1+ , 1)(1) 1

Explorables = { v4 }

-r r (2) 3 - rH H (1) 2 © * (2) 2 (1 + 1) 2 © ¡ HH ¡ HH (1) 1 ¡ H j r (3+ , 1) r©© (1 − 1) 1 ¡ H jr r© H HH © * © * © © H ¡ ¡ © © H (0) 1 HH (1) 1 (0 + 1) 1 (1) 1 ª ª H j r¡ j r¡ -r © -vr© v © * ©©

r

(1+ , 1)(1) 1

5

Pozo v6 etiquetado: ¡Aumento!

(1) 1

5

Recorrido aumentador

v5

Explorables = { v3 }

(3− , 1)(2) 3 (4− , 1)

(2) 2

5

Recorrido aumentador

at

(2) 2

5

Explorables = { v3 , v4 }

Pozo v6 etiquetado: ¡Aumento!

Explorables = { v3 }

(0, ∞)

-rH (0) 2 ¡ HH (1) 1 ¡ H j r (3+ , 1 rH © © * © HH ¡ © (1) 1 (0) 1 ª H j r¡ -r © v © * ©©

em

(1+ , 1)(1) 1

(1+ , 1)(1) 3 (2+ , 1)

(1) 2

r

(1+ , 1)(1) 1

ic

-r r © ©* ¡HH (0) 2 © HH (1) 1 ¡ j r v6 rH © © * © HH ¡ (0) 1 ª j r¡ H -r©© (1) 1

at

(1+ , 1)(1) 3 (2+ , 1)

* © ©©

(1) 2

5

Explorables = { v2 , v4 }

(1) 2

-r (0) 2 ¡HHH (1) 1 ¡ H jr rH © © * v6 © HH ¡ (0) 1 ª H j r¡ -r ©© (1) 1 v

r

.c

v4

-v3H r (0) 2 ¡ HH (1) 1 ¡ H j r v6 r© HH © * © ¡ © (1) 1 (0) 1 HH ª j r¡ -r © v © * ©©

a1

(0, ∞)

(1+ , 1)(1) 3 (2+ , 1)

(1+ , 1)(1) 3

(1) 2

om

v2 (1) 3 v3 r -H r © * (0) 2 © HH ¡ (1) 1 ¡ H j r v6 © rH© © * © HH ¡ (0) 1 ª j r¡ H - r©© (1) 1 (1) 2

v1

v2

r

(2) 3

4

(1) 1

-v3r H (2) 2 ¡ HH (0) 1 ¡ H jr r© HH © * v6 © ¡ (1) 1 HH ª j r¡ -vr©© (1) 1 v © * ©©

(2) 2

5

Exploramos v1 y Explorables = {} . FIN

Observaciones 42.? Aunque en el estudio de las redes y los ejemplos usados tenemos un flujo dado a la red, no es necesario sino que puede usarse como flujo inicial cero en cada arco. ? Para nosotros, una red tiene una sola fuente y un s´olo pozo, pero si tenemos varias fuentes y/o pozos, puede aplicarse todo lo anterior sin m´as que construir una nueva red con una sola fuente y/o un solo pozo. En efecto si tenemos varias fuentes como s1 y s2 , a˜ nadimos un nuevo v´ertice s y dos arcos de s a s1 y de s a s2 . La capacidad del nuevo arco a s1 ser´a la suma de las capacidades de los arcos salientes de s1 y el flujo la suma de los flujos; y lo mismo para el otro arco. Si tenemos varios pozos, a˜ nadimos un nuevo pozo conectado desde los otros pozos y de manera similar se obtienen las capacidades y flujos.

Prof: Jos´ e Antonio Abia Vian

I.T.I. en Electricidad