PUERTA | PUERTA CS 2013 | Pregunta 18

¿Cuáles de las siguientes afirmaciones son VERDADERAS?

1. The problem of determining whether there exists
   a cycle in an undirected graph is in P.
2. The problem of determining whether there exists
   a cycle in an undirected graph is in NP.
3. If a problem A is NP-Complete, there exists a 
   non-deterministic polynomial time algorithm to solve A. 

(A) 1, 2 y 3
(B) 1 y 2 solamente
(C) 2 y 3 solamente
(D) 1 y 3 solamente

Respuesta: (A)
Explicación: 1. Podemos usar BFS o DFS para encontrar si hay un ciclo en un gráfico no dirigido. Por ejemplo, consulte Implementación basada en DFS para detectar ciclos en un gráfico no dirigido . La complejidad del tiempo es O(V+E) que es polinomial.

2. Si un problema está en P, definitivamente está en NP (se puede verificar en tiempo polinomial). Ver NP-Completitud

3. Cierto. Ver Ver NP-

Cuestionario de completitud de esta pregunta