Planteamiento del problema: Optimización de redes
Primera parte
Nos invitan a participar en un proyecto de telecomunicaciones en el que se habrán de colocar enlaces de fibra óptica para comunicar las redes de cómputo internas de un grupo de inmuebles en nuestra ciudad.
Una primera idea, que en teoría funcionaría muy bien, es colocar un enlace entre cada pareja de edificios. Si, por ejemplo, son 5 edificios, como en la siguiente figura, de cada uno saldrían 4 enlaces a los otros edificios.
Pregunta
¿Cuántos enlaces habría que colocar para comunicar 10 edificios todos con todos?
Ve pensando cómo calcularías esta cantidad si de
antemano supieras la respuesta para 9 edificios. Estudiaremos
esta útil estrategia más adelante.
La tecnología de fibra óptica permite transmitir a velocidades muy altas y basta con que exista un camino para ir de un inmueble a otro, es decir, podemos comunicar dos puntos siempre y cuando exista una ruta entre ellos aunque tengamos que ir pasando por puntos intermedios.
Para darnos una mejor idea de lo que entendemos por camino o ruta, vemos que en la figura de arriba, para cualquier par de edificios podemos encontrar una ruta que los conecte pero que además pase primero por los otros tres.
Una cuestión importante es que este tipo de enlaces digitales suelen ser costosos porque hay que colocar físicamente un cable, ya sea de forma subterránea o usando los postes de la calle. Por esta razón es que la idea de conectar los edificios, todos con todos, no es económicamente viable.
El proyecto al que nos invitan considera 8 inmuebles (A, B, C, D, E, F, G y H) y tiene el siguiente cuadro de costos asociados en cientos de miles de pesos.
| B | C | D | E | F | G | H | |
|---|---|---|---|---|---|---|---|
| A | 1 | 2 | 5 | 1 | 12 | 10 | 1 |
| B | 3 | 8 | 2 | 1 | 2 | 4 | |
| C | 6 | 1 | 10 | 9 | 8 | ||
| D | 8 | 3 | 2 | 1 | |||
| E | 1 | 8 | 12 | ||||
| F | 3 | 7 | |||||
| G | 9 |
A uno de nuestros compañeros el cuadro le parece un poco raro: la A no aparece en las columnas, la H no está en los reglones y además casi la mitad está vacío.
Preguntas
¿Está mal hecho el cuadro? ¿Falta información?
Explica cómo es que debemos interpretar o, en su caso, arreglar este cuadro.
Una vez que tenemos claro el significado de los valores en el cuadro, lo que requerimos determinar es la lista de enlaces a instalar, misma que debe ser tal que:
- la suma de los costos sea la menor posible, y
- existan rutas entre cualquier par de puntos.
Preguntas
¿Cuál es el número mínimo de enlaces que requerimos para
conectar los 8 edificios? ¿Y si fuera un número más grande,
digamos cien o mil?
¿Nos serviría conocer de antemano la respuesta para 7
edificios, para 99 o para 999, según el caso?