ensayos

5. REDES – FLUJOS
Red es un grafo ponderado, con un nodo a llamado fuente y otro nodo z llamado pozo, terminal o resumidero (sink).
Se llama red de transporte cuando a cada arco u de la red se lopondera asignándole un par de números enteros, positivos mediante las funciones capacidad, k (u), y flujo, ϕ (u).
W (u) = (k (u), ϕ(u))
K (u) es la capacidad o cota superior de lo que puede transportar el arco u y ϕ (u) el flujo o la cantidad de sustancia que realmente transporta el arco u. Una red de transporte modela problemasdel tipo:
- maximizar el flujo de petróleo, a través de una gran red de oleoductos;
- maximizar el número de llamadas telefónicas en la red de telefonía.
5.1 Corte mínimo – flujo máximoDefinición: Un corte en la red N es el conjunto de los arcos incidentes hacia el exterior de P.
(P, Pc) = {(x,y) , x ∈P, y ∈ Pc, P U Pc = X, P∩Pc = ∅
Definición: Corte a-z(fuente-terminal) es aquel en que a ∈P y z ∈Pc.
Definición: Capacidad de un corte (P,Pc) viene dada por k(P,Pc) = u∈corte k(u) .
Definición: Flujo a-z, (flujo fuente-terminal) en una red N, es aquel enel que ϕ (u) ∀ u ∈ U, los nodos fuente a y pozo z satisfacen las siguientes condiciones:
a) 0 ≤ ϕ (u) ≤k (u) ∀ u ∈U
b) ϕ (u) = 0, ∀ u ∈ I -(a) y ∀u ∈I+ (z)
c) ∀ x ≠ a, ∀x ≠ z, u∈I + (x) ϕ (u) = u∈I-(x) ϕ (u)
Cuantificación de un flujo a-z: |ϕ|.
Se define como la suma del flujo que sale de a, (equivalente a decir que es la suma del flujo que entra a z). Entonces, una cota superior de |ϕ| es lasuma de las capacidades de los arcos incidentes hacia el exterior de a.
|ϕ| = u∈I + (a) ϕ(u) ≤ u∈I + (a) k(u)


5.2 Bases Para la Construcción de unFlujo Máximo
Arco Saturado El arco u de la red se dice saturado cuando k (u) = ϕ (u); La holgura de un arco u es la cantidad libre de su capacidad, aún pasible de utilizar y se nota s(u) = k(u) -...