¿Cómo encontrar un ciclo que contiene un conjunto de nodos en un gráfico?

Question

Dado un grafo no dirigido G = (V, E) y un conjunto de nodos P. I necesidad de encontrar un ciclo (no el ciclo de longitud más corta) que contiene estos nodos? ¿Cómo puedo encontrar este ciclo?

Answer 1

Contiene hamiltoniano Ciclo (para P = V), por lo tanto, el problema de decisión (el hecho de saber si existe tal cosa) es NP-completo. Por lo tanto no hay ningún algoritmo eficiente a menos que P = NP.

Answer 2

Probablemente sería comenzar a diseñar el algoritmo mediante la elección del primer nodo en P (llamémosle P [0]), a continuación, ejecutar una búsqueda en profundidad de P [0], tomando nota de cualquier momento P [0] es nuevo alcanzado. Usted tendría que almacenar la ruta tomada para volver a su alcance P [0] (o por lo menos si se han alcanzado los otros nodos de P) para que sepa que cualquier ciclo que encuentre contiene todos los nodos en P. Tiempo de Reproducción debería ser el mismo que para la búsqueda en profundidad, que creo que es O (V + E).

Alguien puede llegar a una solución mejor, y ciertos heurística puede ser aplicado a la ayuda, sino que debe empezar. (Por ejemplo, es posible concluir que debe empezar en el nodo de P con los bordes menor número en vez de a partir de P [0].)

Editar

Uno más que pensé ... Al llegar a otro nodo P a través de su búsqueda en profundidad, no hay necesidad de que el DFS nunca para "empezar de nuevo" de los caminos que comienzan o muy a tener en cuenta que no lo hacen incluir este nodo recién encontrado. Esta propiedad podría ayudar a su algoritmo de terminar más rápidamente en el caso en que no existe tal ciclo.

Además de edición:

No importa la última edición - sería sólo funcionan si se pueda determinar que no hay ningún nodo en P en un camino diferente entre P [0] y el nodo de P llegado que no puede ser alcanzado de otra manera, y nosotros no sabría que con seguridad sin hacer todo el DFS.

En cuanto a la respuesta acerca de los ciclos hamiltonianos, no sé cómo la detección de ciclos en el problema en cuestión es NP-completo. Sí, tendríamos que atravesar toda la gráfica (todos los vértices y aristas) accesible desde el punto de inicio para determinar si existe un ciclo que satisfacen los criterios del problema en cuestión. Además, sería necesario saber al entrar en contacto con un vértice visitado previamente cuál es el "camino a seguir" del vértice sería la de determinar si hay un ciclo que satisfacen los criterios. Dado que no se preocupan por el menor de dichos ciclos, sin embargo, no estoy seguro de cómo estamos tratando de encontrar necesariamente un ciclo de Hamilton. El cuidado de iluminar?