Satan dominara el mundo

Modelos de Redes
2

Muelle=a
b
e
c
d
z=Refinería
5
3
2
4
4
2
Figura 6.1.1 Red de transporte
2

Muelle=a
b
e
c
dz=Refinería
5
3
2
4
4
2
Figura 6.1.1 Red de transporte
Consideramos la gráfica dirigida de la figura 6.1.1, la cual representa una redde tuberías de petróleo. El petróleo se descarga del muelle a y se bombea a través de una red hasta la refinería z, los vértices b, c, d ye representan estaciones de bombeo intermedias. Las aristas dirigidas representan tuberías e indican la dirección en la cual puede fluirel petróleo. Lo números sobre las aristas representan las capacidades de las tuberías. El problema consiste en determinar una forma demaximizar el flujo del muelle a la refinería y calcular el valor de este flujo máximo. La figura 6.1.1 representa una red de transporteDefinición 6.1.1
Una red de transporte es una gráfica dirigida, simple, con pesos que satisface:
a) Un vértice Fijo, la fuente, no tienearista de entrada.
b) Un vértice fijo, el sumidero, no tiene arista de salida.
c) El peso Cij de la arista dirigida (i, j), llamadola capacidad de (i, j), es un número no negativo.
Ejemplo 6.1.2
La grafica de la figura 6.1.1 es una red de transporte, la fuente es elvértice a y el sumidero es el vértice z. la capacidad de la arista (a, b) , Cab, es 3, y la capacidad de la arista (b, c), Cbc, es 2.