Problema del árbol de Steiner
El problema del árbol de Steiner , o el problema del árbol de Steiner mínimo , llamado así por Jakob Steiner , es un término genérico para una clase de problemas en la optimización combinatoria . Si bien los problemas del árbol de Steiner pueden formularse en varios entornos, todos requieren una interconexión óptima para un conjunto dado de objetos y una función objetivo predefinida. Una variante bien conocida, que a menudo se usa como sinónimo del término problema del árbol de Steiner, es el problema del árbol de Steiner en los gráficos . Dado un gráfico no dirigido con pesos de aristas no negativos y un subconjunto de vértices, generalmente denominados terminales, el problema del árbol de Steiner en los gráficos requiere unaárbol de peso mínimo que contiene todos los terminales (pero puede incluir vértices adicionales). Otras variantes conocidas son el problema del árbol de Steiner euclidiano y el problema del árbol de Steiner mínimo rectilíneo .
El problema del árbol de Steiner en los gráficos puede verse como una generalización de otros dos famosos problemas de optimización combinatoria: el problema de la ruta más corta (no negativa) y el problema del árbol de expansión mínimo . Si un problema de árbol de Steiner en gráficos contiene exactamente dos terminales, se reduce a encontrar el camino más corto. Si, por el contrario, todos los vértices son terminales, el problema del árbol de Steiner en los gráficos es equivalente al árbol de expansión mínimo. Sin embargo, mientras que tanto la ruta más corta no negativa como el problema del árbol de expansión mínimo se pueden resolver en tiempo polinomial, la variante de decisión del problema del árbol de Steiner en los gráficos es NP-completa (lo que implica que la variante de optimización es NP-dura); de hecho, la variante de decisión estaba entre los 21 problemas NP-completos originales de Karp . El problema del árbol de Steiner en gráficos tiene aplicaciones en el diseño de circuitos o redes . Sin embargo, las aplicaciones prácticas generalmente requieren variaciones, lo que da lugar a una multitud de variantes de problemas del árbol de Steiner.
La mayoría de las versiones del problema del árbol de Steiner son NP-hard , pero algunos casos restringidos pueden resolverse en tiempo polinomial . A pesar de la complejidad pesimista del peor de los casos, varias variantes del problema del árbol de Steiner, incluido el problema del árbol de Steiner en los gráficos y el problema del árbol de Steiner rectilíneo, se pueden resolver de manera eficiente en la práctica, incluso para problemas del mundo real a gran escala. [1] [2]
El problema original se planteó en la forma que se conoce como el problema del árbol de Steiner euclidiano o el problema del árbol de Steiner geométrico : Dados N puntos en el plano , el objetivo es conectarlos mediante líneas de longitud total mínima de tal manera que dos los puntos pueden estar interconectados por segmentos de línea, ya sea directamente o mediante otros puntos y segmentos de línea. Se puede mostrar que los segmentos de la línea de conexión no se cruzan entre sí excepto en los puntos finales y forman un árbol, de ahí el nombre del problema.
El problema de N = 3 se ha considerado durante mucho tiempo y se ha extendido rápidamente al problema de encontrar una red en estrella con un solo concentrador que se conecte a todos los N puntos dados, de longitud total mínima. Sin embargo, aunque el problema completo del árbol de Steiner fue formulado en una carta de Gauss , su primer tratamiento serio fue en un artículo de 1934 escrito en checo por Vojtěch Jarník y Miloš Kössler . Este artículo se pasó por alto durante mucho tiempo, pero ya contiene "prácticamente todas las propiedades generales de los árboles de Steiner" atribuidas posteriormente a otros investigadores, incluida la generalización del problema desde el plano a dimensiones superiores. [3]
Para el problema Euclidiano de Steiner, los puntos agregados al gráfico ( puntos de Steiner ) deben tener un grado de tres, y los tres bordes incidentes a dicho punto deben formar tres ángulos de 120 grados (ver punto de Fermat ). De ello se deduce que el número máximo de puntos de Steiner que puede tener un árbol de Steiner es N - 2, donde N es el número inicial de puntos dados.
