El á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.
Árbol de Steiner para tres puntos A, B y C. Nótese que no hay conexiones directas entre ellos. El punto de Steiner S está puesto en el punto de Fermat del triánguloABC.
Solución para cuatro puntos. Nótese que hay dos puntos de Steiner, S1 y S2
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.
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] Reductibilidad entre problemas combinatorios (en inglés)
Datos:Q1764144
Multimedia:Steiner tree problem
Agosto 10, 2021
Árbol, steiner, este, artículo, sección, necesita, referencias, aparezcan, publicación, acreditada, este, aviso, puesto, noviembre, 2012, árbol, steiner, nombrado, honor, jakob, steiner, problema, optimización, combinatoria, consistente, buscar, interconexión,. Este articulo o seccion necesita referencias que aparezcan en una publicacion acreditada Este aviso fue puesto el 22 de noviembre de 2012 El arbol de Steiner nombrado en honor a Jakob Steiner es un problema de optimizacion combinatoria consistente en buscar la interconexion mas corta para un conjunto de elementos dado Es superficialmente similar al problema del arbol recubridor minimo dado un conjunto V de puntos vertices interconectalos por la red grafica de menor longitud donde la longitud es la suma de las medidas de todos los lados Arbol de Steiner para tres puntos A B y C Notese que no hay conexiones directas entre ellos El punto de Steiner S esta puesto en el punto de Fermat del triangulo ABC Solucion para cuatro puntos Notese que hay dos puntos de Steiner S1 y S2 La diferencia entre el problema del arbol de Steiner y el del arbol recubridor es que en el primero se pueden anadir vertices intermedios y lados extras al grafo con el fin de reducir la longitud del arbol recubridor Los vertices introducidos para decrecer la longitud total de las conexiones son conocidos como puntos de Steiner Ha sido demostrado que la conexion resultante es un arbol llamado arbol de Steiner Pueden existir varios arboles de Steiner para un conjunto dado de vertices iniciales El arbol de Steiner tiene aplicaciones en el diseno de circuitos electricos y redes de telecomunicaciones La mayoria 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 polinomico sin embargo en la practica se usa la heuristica en su lugar Definicion EditarDado un grafo G V E displaystyle G V E un subconjunto de vertices S V displaystyle S subset V una funcion de pesos f E Z displaystyle f E rightarrow mathbb Z minimizar el costo del arbol que conecta todos los elementos de S displaystyle S Referencias EditarEnlaces externos Editar 1 Reductibilidad entre problemas combinatorios en ingles Datos Q1764144 Multimedia Steiner tree problemObtenido de https es wikipedia org w index php title Arbol de Steiner amp oldid 119034914, wikipedia, wiki, leyendo, leer, libro, biblioteca,
