Gregorio Hernández Peñalver Curso 07-08
Departamento de Matemática Aplicada, Facultad de Informática, UPM Teoría de Grafos
EJERCICIOS DEL TEMA 5
5.1. Encontrar un flujo máximo y un corte mínimo para las siguientes redes: (El peso de cada arista
indica su capacidad)
2 16
4
5 10 20
3 7 6 3 1
22
2
4 14 17 15 10 t
s t
s
1 1 8 19
1 21 5 12
6 4 9
3 2
18 11
2
5.2. Una empresa minera tiene tres yacimientos m, 8 6
m’, m’’. El mineral extraído se transporta a m p
través de la red de la figura a tres plantas de 4 6
6
6 5
procesado. La cantidad de mineral que puede ser
5 6
extraída de los yacimientos m, m’, y m’’ es de 5, p'
m'
10 y 15 toneladas diarias, respectivamente. En 6
8 6 6
cuanto a las plantas de procesado su capacidad es 5
de 14 toneladas diarias en la planta p, 9 en la
m'' p''
planta p’, y 7 en la planta p’’. Determina la 7 6
cantidad máxima de mineral que puede ser
extraída y procesada en un único día.
5.3. Un convoy de suministros debe transportar 6 tipos de equipamiento diferente a un centro de
refugiados. El material de cada tipo está embalado en cuatro contenedores. Se dispone para el
transporte de 5 aeroplanos que pueden cargar 7, 6, 5, 4 y 3 contenedores, respectivamente. Si no
queremos enviar dos contenedores de un mismo tipo en ningún aeroplano, ¿se puede efectuar el
transporte en un solo viaje?
5.4. Una empresa de maquinaria agrícola debe enviar tractores desde las plantas de montaje s y s' hasta
los centros de distribución t y t', a lo largo de la red de transporte indicada en la figura, donde la
capacidad de cada tramo se indica por la etiqueta del arco correspondiente. Además, los nodos de
distribución intermedios A y B tienen una capacidad de almacenamiento limitada, 70 y 110
unidades respectivamente. ¿Cuántos tractores puede enviar?
80 A 90 90
s t
90 70 20 80
s' 110 B 110 70 t'
5.5. Determinar si las siguientes redes son viables, hallando en caso afirmativo un flujo máximo de s a
t. La etiqueta de cada arco indica el intervalo de flujo permitido
3,5 6,8 3,6
1,4 4,9
0,6 4,4 0,1 t
t s
s
3,6 1,3 3,8
0,2 0,7
1
Gregorio Hernández Peñalver Curso 07-08
Departamento de Matemática Aplicada, Facultad de Informática, UPM Teoría de Grafos
2 8
5.6. La red de vías rápidas que enlazan las ciudades
C y C' se presenta en la figura de la derecha. 2 4
4 5 4
Se ha decidido instalar controles en la
red de modo que todo vehículo que 6 6
C 3 C'
salga de C pase, como mínimo, un
control antes de llegar a C'. La etiqueta 7
8 3 3
de cada arco indica el coste de 7
establecer un control en el tramo
correspondiente. ¿Dónde se deben instalar los 4
controles de modo que se minimice el coste total?
5.7. Tras un terremoto se envían camiones con víveres
desde la ciudad C a la ciudad C'. Los caminos
pueden haber quedado bloqueados por lo que
se piensa enviar camiones por diferentes
rutas, de modo que dos rutas no tengan C C'
ningún tramo común. ¿Cuál es el
máximo número de convoyes con
diferentes rutas que se pueden organizar? El mapa
de carreteras es el de la figura
5.8. En la planta de montaje de la empresa MOTORIA hay una red de cintas transportadoras, que se
representa en la figura, para la instalación de las distintas componentes de cada motor. La red
posee tres estaciones de entrada, P1, P2 y P3, con una capacidad de admisión diaria de 600, 500 y
500 carcasas de motor respectivamente, aunque en el momento actual sólo se reciben 300 carcasas
diarias. Las etiquetas de cada cinta indican su capacidad de trabajo diaria y, en recuadro, el ritmo
al que se trabaja hoy (en centenas).
a) ¿Cuál es el número máximo de motores que se podrían montar en un día?
b) Se desean instalar arcos de pintura por impregnación en algunas cintas para abreviar el tiempo
de fabricación. El coste de la instalación en cada cinta es proporcional a su capacidad. ¿En qué
cintas hay colocarlos para minimizar el coste?
A B
P1
4 2 3 2
1 6
3 1
2 3
1 0
5 3 6 3 4 4
P2 R
C D
2 1 2 3 2
2 3 2
2 2
P3 E
5.9. La sonda espacial S transmite sus imágenes al Centro Alfa de Seguimiento Espacial a través de la
red de estaciones que aparece en la figura inferior. La etiqueta de cada arco indica la capacidad del
enlace correspondiente para transmitir la información. Para mejorar la calidad de las imágenes se
quieren instalar filtros en algunos enlaces. Sabiendo que el coste del filtro es proporcional a la
capacidad del enlace, ¿dónde se deben instalar los filtros de modo que se minimice el coste total?
2
Gregorio Hernández Peñalver Curso 07-08
Departamento de Matemática Aplicada, Facultad de Informática, UPM Teoría de Grafos
a 13 b
10 2
38 2 7
8
8 7
f
S 1 Alfa
c 26 e 1
24
2
27
5.10. La empresa OILGAS envía el petróleo desde sus pozos hasta la refinería R a través de una red de
oleoductos. Los pozos P1, P2 y P3 tienen una capacidad de extracción de 6000, 5000 y 5000
barriles diarios, pero en el momento actual sólo extraen 3000 barriles diarios cada uno. El petróleo
se transporta hasta la refinería según el gráfico adjunto, donde en la etiqueta de cada tramo de
oleoducto se indica la capacidad total del tramo y la que se utiliza en estos momentos (todo ello en
miles de barriles).
A B
P1
4,2 3,2
3,1 1,0 6,3
2,1
P2 5,3 6,3 4,4 R
C D
2,1 2,2 3,2
4,2
3,2
P3 E
a) ¿Cuál es la máxima cantidad de petróleo que puede fluir por la red?
b) En cada tramo de la red hay una válvula cuyo cierre impide el paso del petróleo, siendo el coste
económico del cierre proporcional a la capacidad del tramo. Si se quisiera interrumpir el suministro
de petróleo a la refinería, ¿qué válvulas habría que cerrar para que el coste fuera mínimo?
5.11. Se desea enviar un flujo de 12 unidades por la red de la figura desde s hasta t. ¿Por dónde se debe
enviar si deseamos que el coste
sea mínimo? ¿Cuál es la
6
máxima cantidad de flujo que se 6 5 2 6
puede enviar? ¿Qué caminos
debemos seguir para que el s 5 3 t
coste sea mínimo? (El peso de 4 6 4 5
cada arista indica su capacidad, 5 4 8
7 2
y el número en recuadro el coste 6
de enviar una unidad de flujo 8 2
por la arista)
Los ejercicios 4 y 8 se pueden entregar hasta el día 17 de abril.
