Árboles de Steiner

Ignacio Larrosa Cañestro, Aug 29, 2016

Los árboles de Steiner son grafos que conectan n puntos, a los que se añaden hasta n-2 puntos auxiliares, puntos de Steiner, de manera que la longitud total se acorte respecto al árbol de expansión mínimo del mismo conjunto de puntos. A los puntos de partida se les suele denominar entonces terminales. El problema del Árbol mínimo de Steiner, consiste en hallar el que tiene longitud total mínima. Si resulta no contener puntos de Steiner, el Árbol mínimo de Steiner coincide con el árbol de expansión mínimo. Si contiene exactamente n-2 puntos de Steiner, se dice que es completo. En este caso, el orden de los terminales es siempre uno y el de los puntos de Steiner tres. El cociente entre la longitud del árbol mínimo de Steiner y la del árbol de expansión mínimo se conoce como razón de Steiner q del conjunto de terminales, y evidentemente siempre es menor o igual que 1. En 1968, Edgar Gilbert y Henry Pollack conjeturaron que era siempre mayor o igual que √3/2 = 0.866025... [Gilbert y Pollack, 1968]. Este valor se alcanza para los vértices de un triángulo equilátero,


  • 1. Punto de Fermat de un triángulo
  • 2. Punto de Fermat - Demostración
  • 3. Árbol de Steiner de un cuadrilátero
  • 4. Árbol de Steiner de un dominó
  • 5. Árbol de Steiner de una escalera de 4 peldaños (no óptimo)
  • 6. Árbol de Steiner de una escalera de 5 peldaños (no óptimo)
  • 7. Árbol de Steiner óptimo de una escalera de 4 peldaños
  • 8. Árbol de Steiner óptimo de una escalera de 5 peldaños
  • 9. Árbol de Steiner mínimo de un pentágono regular

Information