algorithm - problema - teorema de ore demostracion
Algoritmo para encontrar un camino de Hamilton en un DAG (2)
No creo que la declaración de @agassaa sea del todo correcta. Considere el ejemplo simple donde hay tres nodos "A", "B", "C" y bordes A-> B, B-> C, A-> C. Mientras que A tiene dos hijos y C tiene dos padres, A-> B-> C forma un camino hamiltoniano. No es necesario atravesar cada borde del gráfico para que el camino sea Hamiltoniano.
Me refiero al Libro de Skienna sobre Algoritmos.
El problema de probar si un gráfico G contiene una Hamiltonian path es NP-hard , donde una ruta hamiltoniana P es una ruta que visita cada vértice exactamente una vez. No es necesario que haya una ventaja en G desde el vértice final hasta el vértice inicial de P, a diferencia del problema del ciclo hamiltoniano.
Dado un gráfico acíclico dirigido G ( DAG ), proporcione un algoritmo de tiempo O(n + m) para probar si contiene o no una ruta hamiltoniana.
Mi acercamiento,
Estoy planeando usar DFS y Topological sorting . Pero no sabía cómo conectar los dos conceptos para resolver el problema. ¿Cómo se puede usar un ordenamiento topológico para determinar la solución?
¿Alguna sugerencia?
Primero puede ordenar topológicamente el DAG (cada DAG puede ordenarse topológicamente) en O (n + m).
Una vez hecho esto, sabes que el borde va desde los vértices de índice inferior a más alto. Esto significa que existe una ruta hamiltoniana si y solo si hay borde entre vértices consecutivos, por ejemplo,
(1,2), (2,3), ..., (n-1,n).
(Esto se debe a que en un camino hamiltoniano no se puede "volver" y, sin embargo, hay que visitarlos todos, por lo que la única forma es "no saltar")
Puede comprobar esta condición en O (n).
Por lo tanto, la complejidad global es O (m + n).