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.