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.
Algunos casos restringidos pueden ser resueltos por tiempo polinómico, sin embargo en la práctica se usa la heurística en su lugar.
; minimizar el costo del árbol que conecta todos los elementos de
