Problema del árbol de Steiner

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[editar]

Dado un grafo $G=(V,E)$ , un subconjunto de vértices $S\subset V$ , una función de pesos $f:E\rightarrow \mathbb {Z}$ ; minimizar el costo del árbol que conecta todos los elementos de $S$ .