Tarea de Redes
1. Usted debe hacer un viaje en automóvil a una ciudad que nunca ha visitado. Estudia un
plano para determinar la ruta más corta hasta su destino. Según la ruta que elija, hay otras
cinco ciudades (llamadas A, B, C, D, E) por las que puede pasar en el camino. El plano
muestra las millas de cada carretera que son una conexión directa entre dos ciudades sin
que otra intervenga. Estas cifras se resumen en la siguiente tabla, donde un guion indica
que no hay conexión directa sin pasar por otras ciudades.
Ciudad Millas entre ciudades adyacentes
A B C D E Destino
Origen 40 60 50 - - -
A 10 - 70 - -
B 20 55 40 -
C - 50 -
D 10 60
E 80
a) Formule un modelo como un problema de la ruta más corta al trazar una red donde los
nodos son ciudades, los arcos son carreteras y los números la distancia en kilómetros.
b) Use el algoritmo visto en clase para resolver este problema de la ruta más corta
2. Utilice el algoritmo visto en clase para encontrar la ruta más corta a través de las redes a)
y b), en las cuales los números representan las distancias reales entre los nodos
correspondientes.
a)
b)
3. Un aserradero talará árboles en ocho zonas de la misma área. Pero antes debe desarrollar
un sistema de caminos de tierra para tener acceso a cualquier zona desde cualquier otra.
La distancia (en kilometros) entre cada par de zonas es:
Distancia entre pares de zonas
1 2 3 4 5 6 7 8
1 - 1.3 2.1 0.9 0.7 1.8 2.0 1.5
2 1.3 - 0.9 1.8 1.2 2.6 2.3 1.1
3 2.1 0.9 - 2.6 1.7 2.5 1.9 1.0
4 0.9 1.8 2.6 - 0.7 1.6 1.5 0.9
Zona
5 0.7 1.2 1.7 0.7 - 0.9 1.1 0.8
6 1.8 2.6 2.5 1.6 0.9 - 0.6 1.0
7 2.0 2.3 1.9 1.5 1.1 0.6 - 0.5
8 1.5 1.1 1.0 0.9 0.8 1.0 0.5 -
El problema es determinar los pares de zonas entre los que deben construirse caminos para
conectar todas con una longitud de caminos total mínima.
a) Describa cómo se ajusta este problema a la descripción del problema del árbol de
expansión mínima.
b) Utilice el algoritmo visto en clase para resolverlo.
4. El Premiere Bank ha decidido conectar terminales de computadora de cada sucursal a la
computadora central de su oficina matriz mediante líneas telefónicas especiales con
dispositivos de telecomunicaciones. No es necesario que la línea telefónica de una
sucursal esté conectada directamente con la oficina matriz. La conexión puede ser
indirecta a través de otra sucursal que esté conectada (directa o indirectamente) a la
matriz. El único requisito es que exista alguna ruta que conecte a todas las sucursales con
la oficina matriz. El cargo por las líneas telefónicas especiales es directamente
proporcional a la distancia cableada, donde la distancia (en millas) entre cada par de
oficinas es:
Distancia entre pares de oficinas
Principa S.1 S.2 S.3 S.4 S.5
l
Oficina - 19 70 11 27 16
principal 0 5 0 0
Sucursal 1 190 - 10 11 21 50
0 0 5
Sucursal 2 70 10 - 14 12 22
0 0 0 0
Sucursal 3 115 11 14 - 17 80
0 0 5
Sucursal 4 270 21 12 17 - 31
5 0 5 0
Sucursal 5 160 50 22 80 31 -
0 0
La administración desea determinar qué pares de sucursales conectar directamente con las líneas
telefónicas especiales para que todas queden conectadas (de modo directo o indirecto) a la oficina
matriz con un costo total mínimo.
a) Explique cómo se ajusta este problema a la descripción del problema del árbol de
expansión mínima.
b) Utilice el algoritmo visto en clase para resolver el problema.
5. La Texaco Corporation tiene cuatro campos de petróleo, cuatro refinerías y cuatro centros
de distribución. Una fuerte huelga en la industria del transporte ha reducido de manera
considerable la capacidad de Texaco para enviar petróleo de sus campos a las refinierías y
los productos derivados a los centros de distribución. Use unidades en miles de barriles de
petróleo crudo (y su equivalente en productos refinados); las tablas siguientes muestran el
número máximo de unidades que puede enviar al día de cada campo a cada refinería y de
éstas a cada centro de distribución.
Campo Refinería
N. Orleans Charleston Seattle San Luis
Texas 11 7 2 8
California 5 4 8 7
Alaska 7 3 12 6
Medio oeste 8 9 4 15
Refinería Centro de distribución
Pittsburgh Atlanta Kansas City San Francisco
N. Orleans 5 9 6 4
Charleston 8 7 9 5
Seattle 4 6 7 8
San Luis 12 11 9 7
La administración de Texaco desea elaborar un plan para determinar cuántas unidades debe
enviar de cada campo petrolero a cada refinería y de cada refinería a cada centro de distribución
de manera que se maximice el número total de unidades que llegan a los centros de distribución.
a) Bosqueje un plano que muestre la ubicación de los campos, refinerías y centros de
distribución de Texaco. Agregue el flujo del petróleo crudo y de los productos del petróleo
a través de la red de distribución.
b) Dibuje de nuevo la red alineando en una columna los nodos de los campos, en otra los
de refinerías y en una tercera los de centros de distribución. Después agregue arcos para
mostrar el flujo posible.
c) Modifique la red del inciso b) para formular este problema como uno de flujo máximo
con sólo una fuente, un destino y una capacidad de cada arco.
d) Utilice el algoritmo de trayectoria de aumento visto en clase para resolver el problema
de flujo máximo.
6. Considere el problema de flujo máximo que se muestra en la siguiente red, en donde A es el
nodo origen y F el nodo de demanda, mientras que las capacidades son los números que se
muestran junto a los arcos dirigidos.
a) Utilice el algoritmo de la trayectoria de aumento descrito en clase para resolver este
problema.