¿Cuál es el número máximo de nodos que puedo recorrer un grafo no dirigido visitar cada nodo exactamente una vez?

Question

Así que tengo una onu-dirigida de la onu-grafo ponderado. Contiene ciclos. Me gustaría encontrar el camino que visitas la mayoría de los nodos con no repetir las visitas a cualquier nodo. Dado que este es un gráfico de recorrido, usted puede comenzar y terminar en cualquier nodo que te gusta.

La Investigación de fondo: he mirado en el Problema del Viajante (TSP); este problema es diferente y NO le permiten terminar donde empezó a partir y no hay pesos. He mirado en varios otros algoritmos, pero no he encontrado ninguno adecuado para este problema.

Tamaño de la gráfica: Hay 100 nodos en el gráfico; con 10 nodos desconectados.

Answer 1

Este problema es aún más difícil, es el conocido como camino Hamiltoniano, y NP-completo. No realmente hacer una diferencia si el camino está cerrado (un circuito) o no. Basta con preguntar a los HAM-RUTA problema para cada par de estaciones de todos los bordes y usted podría solucionar el JAMÓN de CIRCUITO.

Answer 2

http://en.wikipedia.org/wiki/Longest_path_problem

En la teoría de grafos y la informática teórica, el camino más largo el problema es el problema de encontrar un camino simple de longitud máxima en un gráfico dado. Un camino que se llama simple si no tiene ninguna repetida vértices, la longitud de una ruta de acceso puede ser medido por su número de los bordes, o (en ponderados gráficos) por la suma de los pesos de sus aristas. En contraste con el problema de la ruta más corta, que se pueden resolver en el polinomio de tiempo en los gráficos sin negativo-de peso ciclos, el más largo ruta problema es NP-duro, lo que significa que no pueda ser resuelto en polinomio tiempo para grafos arbitrarios a menos que P = NP. Más fuerte dureza los resultados son conocidos también muestra que es difícil aproximado. Sin embargo, tiene un tiempo lineal de la solución para los dirigidos acíclicos gráficos, que tiene importantes aplicaciones en la búsqueda de la ruta crítica en problemas de programación.