Resolución del problema
El procedimiento
La idea fundamental detrás del procedimiento que nos lleva a la solución del problema tiene que ver con la forma en la que añadimos un siguiente punto a nuestra solución en construcción.
Tiene que ver con la forma en la que pasamos de \(S_k\) a \(S_{k+1}\) y, por tanto, de \(E_{k-1}\) a \(E_k\).
\[S_k\mathop{\longrightarrow}^?S_{k+1}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ E_{k-1}\mathop{\longrightarrow}^?E_{k}\]
Como referencia para lo que sigue, nos va a ayudar pensar en la manera en la que acabamos de construir la red de respaldo óptima de la página anterior.
Comenzamos
Vamos a suponer que escogemos algún punto de forma arbitraria y construimos \(S_1\).
Pregunta
¿La elección al azar de este primer punto
debe preocuparnos? ¿Será que hay algún punto privilegiado por
el que debamos comenzar?
No, porque en principio todos los puntos deben ser conectados. Al avanzar un poco más quedarás convencido de esto.
Continuamos
Ahora, demos por hecho que tenemos un conjunto de \(k\) puntos \(S_k\) que se enlaza mediante los \(k-1\) enlaces de \(E_{k-1}\). Por ejemplo, \(S_5\) con los enlaces de \(E_4\) en la página anterior.
Pensando en la construcción de la red de respaldo, ¿qué características tiene el siguiente enlace que tomamos para pasar de \(S_5\) a \(S_6\)?
En general, ¿serán estas las mismas características que tiene el siguiente enlace que tomamos en el resto de los pasos, salvo el primero?
Bueno, pues ya sabes lo que hay que hacer, pasa a la siguiente página para practicar este procedimiento.