Según tengo entendido:
1) dado un gráfico G con n vértices y m aristas, DFS es O(n + m)
2) La DFS puede utilizarse para producir una lista de todos los caminos simples entre 2 vértices u y v
Esto significaría que DFS puede producir una lista de todos los caminos simples entre u y v en tiempo polinómico.
Sin embargo, si pudiéramos enumerar todos los caminos simples entre u y v en tiempo polinómico, deberíamos ser capaces de decidir si G tiene un camino de Hamilton entre u y v en tiempo polinómico.
Dado que determinar si G tiene un Camino de Hamilton es NP-Completo, mi entendimiento debe ser incorrecto. Espero que alguien pueda aclarar lo que se me escapa.
0 votos
Tu (2) no me parece cierta. ¿Puede detallar más en qué sentido podría ser cierta esa afirmación?
0 votos
@HenningMakholm Error mío en (2). DFS tarda (n+m) en recorrer un grafo con n vértices y m aristas. Sin embargo, si lo modificamos para que imprima todos los caminos posibles entre todos los pares de vértices, tardaría mucho más.