Algunas aplicaciones del problema del árbol de recubrimiento de coste mínimo:

• Diseño de redes (de telefonía, eléctricas, hidráulicas, de TV por cable, de computadores, de carreteras…)
• Algoritmos aproximados para problemas NP => asignatura “Algoritmia para problemas difíciles”
• Algoritmos de agrupamiento (clustering analysis)
• Aplicaciones indirectas:
  • caminos cuello de botella
  • códigos LDPC para corrección de errores
  • registro de la imagen con entropía de Rényi
  • identificación de rostros en tiempo real
  • reducción de ocupación del almacenamiento de secuencias de aminoácidos de proteínas
  • modelado de interacciones de partículas en flujos turbulentos de fluidos
  • protocolo de autoconfiguración de puentes de red Ethernet para evitar ciclos en una red
  • etc, etc

La historia del estudio de este problema y sus soluciones tiene también su miga… Recomendable echar un vistazo al artículo:

Ronald L. Graham y Pavol Hell: ”On the history of the minimum spanning tree problem”, Annals of the History of Computing, vol. 7, no. 1, pp. 43-57, January 1985 (accesible aquí; copia local, acceso restringido).