Problema del árbol de Steiner

¿Qué es el árbol de Steiner? Dado un gráfico y un subconjunto de vértices en el gráfico, un árbol de Steiner se extiende a través del subconjunto dado. El árbol de Steiner puede contener algunos vértices que no están en el subconjunto dado pero que se utilizan para conectar los vértices del subconjunto. El conjunto dado de vértices se denomina vértices terminales y otros vértices que se utilizan para construir el árbol de Steiner se denominan vértices de Steiner . El problema del árbol de Steiner es encontrar el costo mínimo del árbol de Steiner. Vea a continuación un ejemplo. Árbol de expansión frente a árbol de Steiner El árbol de expansión mínimo es un árbol de peso mínimo que abarca todos los vértices. Si los vértices del subconjunto (o terminal) dados son iguales al conjunto de todos los vértices en el problema del árbol de Steiner, entonces el problema se convierte en el problema del árbol de expansión mínimo. Y si el subconjunto dado contiene solo dos vértices, entonces es el problema del camino más corto entre dos vértices. Descubrir el árbol de expansión mínimo se puede resolver en tiempo polinomial, pero el problema del árbol de Steiner mínimo es NP-difícil y el problema de decisión relacionado es NP-completo. Aplicaciones de Steiner Tree Cualquier situación en la que la tarea sea minimizar el costo de conexión entre algunas ubicaciones importantes como VLSI Design, redes informáticas, etc. Algoritmo aproximado basado en la ruta más cortaDado que el problema del árbol de Steiner es NP-Hard, no existen soluciones de tiempo polinomial que siempre brinden un costo óptimo. Por lo tanto, existen algoritmos aproximados para resolver el mismo. A continuación se muestra un algoritmo aproximado simple.

1) Start with a subtree T consisting of 
   one given terminal vertex
2) While T does not span all terminals
   a) Select a terminal x not in T that is closest 
      to a vertex in T.
   b) Add to T the shortest path that connects x with T

El algoritmo anterior es (2-2/n) aproximado, es decir, garantiza que la solución producida por este algoritmo no sea mayor que esta relación de solución optimizada para un grafo dado con n vértices. También hay mejores algoritmos que proporcionan una mejor proporción. Consulte la referencia a continuación para obtener más detalles. Referencias: www.cs.uu.nl/docs/vakken/an/teoud/an-steiner.ppt Este artículo es una contribución de Shivam Gupta . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.