Sea SHAM 3 el problema de encontrar un ciclo hamiltoniano en una gráfica G = (V,E) con V divisible por 3 y sea DHAM 3 el problema de determinar si existe un ciclo hamiltoniano en dichas gráficas. ¿Cuál de las siguientes es verdadera?
(A) Tanto DHAM 3 como SHAM 3 son NP-hard
(B) SHAM 3 es NP-hard, pero DHAM 3 no lo es
(C) DHAM 3 es NP-hard, pero SHAM 3 no lo es
(D) Ni DHAM 3 ni SHAM 3 es NP-duro
Respuesta: (A)
Explicación:El problema de encontrar si existe o no un Ciclo Hamiltoniano es NP Duro y NP Completo Ambos.
Encontrar un ciclo hamiltoniano en un gráfico G = (V,E) con V divisible por 3 también es NP Difícil.
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