Considere los siguientes dos problemas de gráficas.
1) Dado un gráfico, encuentre si el gráfico tiene un ciclo que visita cada vértice exactamente una vez excepto el primer vértice visitado que debe visitarse nuevamente para completar el ciclo.
2) Dado un gráfico, encuentre si el gráfico tiene un ciclo que visita cada borde exactamente una vez.
¿Cuál de los siguientes es cierto acerca de los dos problemas anteriores?
(A) El problema 1 pertenece al conjunto completo NP y el 2 pertenece al conjunto P
(B) El problema 1 pertenece al conjunto completo P y el 2 pertenece al conjunto completo NP
(C) Ambos problemas pertenecen al conjunto completo P
(D) Ambos problemas pertenecen al conjunto completo NP
Respuesta : (A)
Explicación: El problema 1 es el problema del ciclo hamiltoniano, que es un famoso problema NP completo.
El problema 2 es el problema del circuito de Euler que se puede resolver en tiempo polinomial.
Cuestionario de esta pregunta
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA