Árbol de expansión mínimo: Kruskal y Prim

Pulsa Doce pueblos y recorre el algoritmo de Kruskal paso a paso. Examina las 66 carreteras posibles empezando por las más cortas. Por eso K–L, de 13,89 km, se acepta de inmediato, mientras que C–D y B–C se rechazan: el camino rojo ya conecta sus extremos. Cambia a Prim, que hace crecer una sola red desde A. Elige las carreteras en otro orden, deja K–L para el final, rechaza las mismas dos y termina con las mismas 11 carreteras y los mismos 199,04 km. Ambos siguen una misma regla, la propiedad del corte. Divide los puntos en dos grupos como quieras: si no hay dos carreteras de igual longitud, la más corta que une ambos grupos pertenece al árbol de expansión mínimo. Si la excluyes, el camino del árbol entre sus extremos tendrá que cruzar la separación por alguna carretera más larga; al intercambiarlas, el árbol se acorta. En cada paso de Prim, la red sombreada ocupa uno de los lados de un corte. Pulsa ahora Vecino más próximo. Es el bucle de Prim con un solo cambio: busca desde el último pueblo alcanzado, no desde la red entera. En el tercer paso elige D–F, de 17,96 km, aunque A–C, de 17,67 km, cruza el corte. Pasa de largo ante A–C siete veces más y termina con un 10,76% de longitud adicional. Otakar Borůvka, el primero en resolver el problema, lo formuló en 1926 pensando en la red eléctrica del sur de Moravia. Habló de puntos cuyas «distancias mutuas son diferentes»: la misma condición que impide que Kruskal y Prim discrepen.

Pulsa Pueblos en círculo. Diez pueblos rodean un lago y el árbol recorre la orilla salvo por un tramo: el hueco más ancho, entre J y A. En línea recta, los separan 25,89 km; por el árbol, 128,30 km, una distancia 4,96 veces mayor, pues la única ruta entre ambos atraviesa toda la red. La línea morada discontinua señala la pareja; arrastra cualquier pueblo y la página encontrará el nuevo peor caso. Un árbol de expansión mínimo reduce al máximo la longitud total, pero no garantiza nada sobre la distancia entre dos pueblos concretos. Construir también la carretera de 25,89 km convertiría el trayecto de A a J en un recorrido directo. Decidir si compensa añadirla exige estudiar los viajes: es el problema del camino más corto, que continúa en la página dedicada al algoritmo de Dijkstra.

Pulsa Tres localidades. Están separadas por 40 km, así que el árbol mide 80,00 km. Un enlace central donde confluyen tres carreteras a 120° permite conectarlas con 69,28 km, un 13,40% menos, es decir, 1 − √3/2. Pulsa Cuatro en un cuadrado: dos enlaces ahorran un 8,93%. Vuelve al triángulo y arrastra C hacia A y B. En cuanto el ángulo de C supera los 120°, el enlace se desplaza hasta C; a partir de ahí, ningún enlace aporta ventaja. Hallar los mejores enlaces es el problema del árbol de Steiner. En 1968, Edgar Gilbert y Henry Pollak conjeturaron que el triángulo equilátero representa el peor caso: para ningún conjunto de puntos del plano puede un árbol de Steiner medir menos de √3/2 de su árbol de expansión mínimo. Du y Hwang publicaron una demostración en 1990. En 2010, Innami y otros tres investigadores aportaron indicios de que su paso fundamental era incorrecto. Ivanov y Tuzhilin, que señalaban lagunas en la prueba desde 2002, escribieron en 2012 que la conjetura seguía abierta. Una recopilación de 2025 sobre problemas abiertos de árboles de Steiner aún la incluye. Nadie sabe si alguna disposición de puntos permite ahorrar más que el 13,40% del triángulo.