Formalización del problema
La versión general del 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.
Sabemos que la cantidad de enlaces o
miembros del conjunto de enlaces que soluciona el problema es
\(n-1\).
Sabemos también que el número de costos del
cuadro, que es también el número de enlaces necesarios para
conectar los puntos todos con todos es\[\frac{n(n-1)}2\]
Ahora que tenemos claro lo que debemos hacer, que de hecho hemos practicado repetidamente en el apartado de exploración, pasemos a resolver el problema.