Resolución del problema

El problema

Dados \(n\) puntos y un cuadro de costos de todos los enlaces requeridos para comunicar cada pareja de puntos, debemos escoger una lista de enlaces de tal forma que la suma de los costos correspondientes sea la menor posible, pero que haya siempre una ruta que permita comunicar dos puntos cualesquiera.

Dos conjuntos de puntos

Algo que notamos con facilidad cuando intentamos encontrar la solución al problema en cualquiera de los espacios interactivos, es que en cuanto comenzamos a marcar enlaces, incluyéndolos como parte de la solución, dividimos el conjunto de puntos en los siguientes dos subconjuntos complementarios:

  1. El subconjunto de puntos que ya están enlazados con algún otro, que podemos también denominar como el conjunto de los puntos de la solución en construcción.

  2. El conjunto de puntos aislados, es decir, el de los puntos que aún no han sido incluidos en la solución en construcción.

Lo anterior es tan obvio y evidente que ni siquiera le habíamos dado importancia, aunque al buscar la solución debíamos tener cuidado de ir incluyendo todos los puntos.

Vamos a denotar como \(S_1\) al conjunto de la solución compuesto por un primer punto. Llamaremos \(S_2\) al mismo conjunto cuando tenga dos puntos y a \(S_k\) al conjunto de puntos de la solución en construcción cuando llevemos incluidos \(k\) puntos. Con esta notación \(S_n\) será nuestra solución e incluirá a todos los puntos.

De forma paralela, vamos construyendo el conjunto de enlaces de nuestra solución. Denotaremos \(E_1\) al conjunto de enlaces de la solución en construcción compuesto por un primer enlace. Llamaremos \(E_2\) al mismo conjunto cuando tenga dos enlaces y a \(E_k\) al conjunto de enlaces de la solución en construcción cuando llevemos incluidos \(k\) enlaces. Con esta notación \(E_{n-1}\) será nuestra solución e incluirá a todos los enlaces necesarios para conectar los \(n\) puntos.

Para tener siempre un conjunto \(E_{k-1}\) asociado a un conjunto \(S_k\) añadiremos el conjunto \(E_0\) que es el conjunto de enlaces correspondiente a \(S_1\). ¿Cuál es?

La siguiente es la misma escena que usamos en la primera página de la exploración y corresponde a los datos de la red de respaldo conformada por enlaces con antenas de radio. En esta ocasión te pedimos que construyas la solución paso a paso e identifiques los conjuntos \(S_1,S_2,S_3,S_4,S_5,S_6,S_7,S_8\), así como los conjuntos \(E_0,E_1,E_2,E_3,E_4,E_5,E_6,E_7\).

Si en el espacio anterior tomas sucesivamente los enlaces AB, BC, CD, DE, EF, FG y GH, entonces encuentras una solución correcta. ¿Cuáles son los conjuntos \(S_1,S_2,S_3,S_4,S_5,S_6,S_7,S_8\) y \(E_0,E_1,E_2,E_3,E_4,E_5,E_6,E_7\) si comienzas por el punto A?

\[S_1=\{A\},\ \ E_0=\{\}\] \[S_2=\{A,B\},\ \ E_1=\{AB\}\] \[S_3=\{A,B,C\},\ \ E_2=\{AB,BC\}\] \[S_4=\{A,B,C,D\},\ \ E_3=\{AB,BC,CD\},\] \[S_5=\{A,B,C,D,E\},\ \ E_4=\{AB,BC,CD,DE\},\] \[S_6=\{A,B,C,D,E,F\},\ \ E_5=\{AB,BC,CD,DE,EF\},\] \[S_7=\{A,B,C,D,E,F,G\},\ \ E_6=\{AB,BC,CD,DE,EF,FG\},\] \[S_8=\{A,B,C,D,E,F,G,H\},\ \ E_7=\{AB,BC,CD,DE,EF,FG,GH\}.\]