Problema del árbol de Steiner
![]() | Este artículo o sección necesita referencias que aparezcan en una publicación acreditada. Busca fuentes: «Problema del árbol de Steiner» – noticias · libros · académico · imágenes Este aviso fue puesto el 22 de noviembre de 2012. |
![](http://upload.wikimedia.org/wikipedia/commons/thumb/3/3f/Steiner_3_points.svg/220px-Steiner_3_points.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/e/e4/Steiner_4_points.svg/220px-Steiner_4_points.svg.png)
El problema del árbol de Steiner, nombrado en honor a Jakob Steiner, es un problema de optimización combinatoria consistente en buscar la interconexión más corta para un conjunto de elementos dado. Es superficialmente similar al problema del árbol recubridor mínimo: dado un conjunto V de puntos (vértices), interconectalos por la red gráfica de menor longitud, donde la longitud es la suma de las medidas de todos los lados.
La diferencia entre el problema del árbol de Steiner y el del árbol recubridor es que, en el primero se pueden añadir vértices intermedios y lados extras al grafo con el fin de reducir la longitud del árbol recubridor. Los vértices introducidos para decrecer la longitud total de las conexiones son conocidos como puntos de Steiner. Ha sido demostrado que la conexión resultante es un árbol, llamado árbol de Steiner. Pueden existir varios árboles de Steiner para un conjunto dado de vértices iniciales.
El árbol de Steiner tiene aplicaciones en el diseño de circuitos eléctricos y redes de telecomunicaciones. La mayoría de las versiones del problema de Steiner son NP-completo. De hecho uno de estos pertenece a la lista de 21 problemas NP-completos de Karp. Algunos casos restringidos pueden ser resueltos por tiempo polinómico, sin embargo en la práctica se usa la heurística en su lugar.
Definición
Dado un grafo , un subconjunto de vértices , una función de pesos ; minimizar el costo del árbol que conecta todos los elementos de .
Referencias
Enlaces externos
- [1] Archivado el 19 de agosto de 2016 en Wayback Machine. Reductibilidad entre problemas combinatorios (en inglés)
Datos: Q1764144
Multimedia: Steiner tree problem / Q1764144