Рубрики

ВОРОТА | GATE CS 2013 | Вопрос 18

Какие из следующих утверждений являются ИСТИННЫМИ?

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. 

(А) 1, 2 и 3
(B) 1 и 2 только
(C) только 2 и 3
(D) 1 и 3 только

Ответ: (А)
Объяснение: 1. Мы можем использовать BFS или DFS, чтобы определить, существует ли цикл в неориентированном графе. Например, см. Реализацию на основе DFS, чтобы обнаружить цикл в неориентированном графе . Временная сложность O (V + E), которая является полиномиальной.

2. Если проблема в P, то она определенно в NP (может быть проверена за полиномиальное время). Смотри NP-Полноту

Рекомендуемые посты:

ВОРОТА | GATE CS 2013 | Вопрос 18

0.00 (0%) 0 votes