Dado un gráfico dirigido con bordes ponderados, qué algoritmo se puede usar para dar un subgrupo que tiene un peso mínimo, pero permite el movimiento desde cualquier vértice a cualquier otro vértice en el gráfico (bajo la suposición de que siempre existen caminos entre dos vértices).Un árbol de expansión mínimo bidireccional de un gráfico dirigido
¿Existe tal algoritmo?
Esto parece ser NP-Hard: el peso mínimo fuertemente conectado, abarcando el problema del subgráfico.
Creo que el problema del ciclo hamiltoniano puede reducirse a él: dado un gráfico G (V, E), construye un DG dágiraf con peso 1 para los bordes que aparecen y peso 100 (| V | +1) para los bordes que 't. DG tiene un peso mínimo fuertemente conectado que abarca un subgráfico de peso exactamente | V | si y solo si G tiene un ciclo hamiltoniano.
El documento que aquí tiene un algoritmo de aproximación: http://portal.acm.org/citation.cfm?id=844363
A pesar de que no estaban bien a sí mismos, tomar el tiempo para seguir los enlaces de Wikipedia de Vitalii descubierto rápidamente este algoritmo:
http://en.wikipedia.org/wiki/Chu%E2%80%93Liu/Edmonds_algorithm
Partir cada nodo en el gráfico en dos nodos. Un nodo aceptará todos los bordes entrantes al nodo original, y el otro tendrá todos los bordes salientes. Luego, suelta la dirección en todos los bordes, por lo que el gráfico no está dirigido. Luego puede ejecutar un algoritmo MST estándar en el gráfico (Prim's, Kruskal's) y se asegurará de que cada nodo original pueda ser recorrido por cada otro nodo original.
Lamentablemente, esto no funcionará, ya que agregará bordes innecesarios al gráfico final. Al menos un nodo tendrá un borde adicional conectado, incluso si no necesita tener ese borde. Por ejemplo, en un gráfico con los vértices A, B, C y los bordes AB, BA, BC, CB, AC, CA, la extensión mínima del gráfico puede ser solo los bordes AB, BC, CA. Pero usando su método, esos 3 bordes no se unirían entre sí, y se necesitarían agregar bordes adicionales para terminar el MST. –
elegir cualquier nodo y devolverlo.
Did que quizá decir encontrar el más grande conectados fuertemente subgrafo (menor número de nodos elimina posible), o la mínimo peso que abarca subgrafo (no el traslado de nodos permitidos)?
El título dice 'spanning tree', así que presumo el último. –
@Moron: Ah, me lo perdí :) en cuyo caso, tu respuesta es correcta. –
Este es un Directed Steiner Tree problema. Como Steiner Tree, es NP-Hard.
puede encontrar algunos algoritmos aproximados aquí: algoritmo
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.38.8774&rep=rep1&type=ps
Pero un Steiner Tree dirigido requiere una raíz, ¿no? – highBandWidth
Los algoritmos pueden encontrar el vértice raíz óptimo, pero puede especificar una raíz junto con el conjunto de vértices. – jwinandy
de Edmond sólo asegura que cada nodo en un gráfico será accesible desde la raíz, no es que cada nodo será accesible desde todos los demás nodos. –
Esto es NP-Hard. -1. –
¿Qué tiene que ver la clasificación NP de mi enlace con su relevancia para la pregunta original? – Mathew