Redes transporte estructuras discretas

REDES DE TRANSPORTE 2010

Redes de transporte: El teorema de flujo máximo y corte mínimo

Stella Leirana Mariela Farinacci 2010
1
STELLA LEIRANA-MARIELA FARINACCI

REDES DE TRANSPORTE 2010
Actividad introductoria:
El siguiente grafo representa un sistema de cañerías de transporte de agua que alimenta las piscinas de un complejo vacacional. Por razones de presión y topografía delterreno las cañerías deben estar dispuestas de la siguiente manera:

Observaciones: Los números asociados a cada cañería (arista del grafo) representan el máximo caudal de agua que soporta cada una fi simboliza un posible flujo que circulará por cada cañería, el que no boliza debe superar el máximo caudal indicado. a representa la fuente de agua y z el lugar donde están las piscinas (le llamamossumidero sumidero) El máximo caudal que sale de la fuente es………….. El máximo caudal que puede llegar a las piscinas (sumidero) es………… Encuentra alguna posible distribución del flujo de agua que circula por el sistema de cañerías, sin que colapse ningún caño. Ten en cuenta que: • El sistema de cañerías está trabajando en régimen estacionario, o sea que la cantidad de agua es constante en cada cañería. •El flujo de agua que llega a cada vértice distinto del sumidero y la fuente debe ser el mismo que el que sale de dicho vértice. Completa: f1+f2………….12 f1+f3............f4+f5 f5+f6………….f8+f7 f5+f6………….8 f1+f2………….f9+f7

2

STELLA LEIRANA-MARIELA FARINACCI MARIELA

REDES DE TRANSPORTE 2010
Definición: Sea N=(V,E) un grafo dirigido conexo sin lazos. Diremos que N

es una red, o red detransporte, si se cumplen las siguientes condiciones:
Existe un único vértice a ∈V /ge(a)=0 (el grado de entrada de a es 0). Este vértice es la fuente Existe un único vértice z ∈V , llamado sumidero, /gs(z)=0 El grafo N es ponderado, por lo que existe una función de E en el conjunto de enteros no negativos que asigna a cada arista
e = (v, w) ∈ E una capacidad que se denota c (e) = c(v, w)Actividad:
a) Observa que el grafo utilizado para modelar el problema anterior es una red y determina la función capacidad vinculada al problema, completa:

E = {..............................}
c (a, b)  ......... → c (......,......)  ......... → c (......,......)  ......... →

c:E → Z+
c (......,......)  ......... → c (......,......)  ......... → c (......,......)  ......... → c(......,......)  ......... → c (......,......)  ......... → c (......,......)  ......... →

b) ¿Qué significado le atribuirías, en el contexto del problema a c(a,b)+c(a,g)=12? c) ¿Qué significado le darías a c(d,z)+c(h,z)=11?

Definición: Si N = (V.E) es una red de transporte, f : E → Z + es un flujo de N si: a) f (e) ≤ c (e), ∀e ∈ E b) ∀v ∈V , v ≠ a, v ≠ z, secumpleque

w∈V

∑ f (w, v) =h∑ f (v, h) ∈V

La primera condición especifica que la cantidad de material transportado a lo largo de una arista dada no puede exceder la capacidad de esa arista. La condición (b) pide que la cantidad de material que fluye hacia un vértice v deba ser igual a la cantidad que fluye desde ese vértice. (Excepto la fuente y el sumidero).

3

STELLA LEIRANA-MARIELA FARINACCI

REDES DETRANSPORTE 2010

Ejemplo: Observamos las siguientes redes:

La etiqueta x,y sobre cada arista e, significa x=c(e) e y es el valor asignado a un flujo posible f. La etiqueta en cada arista satisface f (e) ≤ c (e) . En (a), el flujo hacia el vértice g es 5, pero el flujo que sale de g es 2+2=4, por lo tanto, la función f no es un flujo en este caso. La función f de la parte (b) satisface ambascondiciones, por lo que es un flujo de la red dada.

Definición: Sea f un flujo para una red de transporte N=(V,E): a) Una arista e de la red está saturada si f(e) = c(e) b) Si a es la fuente de N, entonces val ( f ) = ∑ f (a, v) es el valor del flujo
v∈V

Ejemplo: Para la red de la figura anterior, {h, d } es la única arista saturada.
El valor del flujo en esta red es val ( f ) = ∑ f (a, v) = f...