Рубрики

ВОРОТА | GATE-CS-2006 | Вопрос 31

Пусть SHAM 3 будет проблемой нахождения гамильтонова цикла в графе G = (V, E) с V, делимым на 3, а DHAM 3 будет проблемой определения, существует ли гамильтонов цикл в таких графах. Что из следующего верно?
(A) Как DHAM 3, так и SHAM 3 являются NP-трудными
(B) SHAM 3 является NP-трудным, но DHAM 3 не является
(C) DHAM 3 является NP-трудным, но SHAM 3 не
(D) Ни DHAM 3, ни SHAM 3 не являются NP-трудными

Ответ: (А)
Пояснение: Проблема нахождения того, существует ли гамильтонов цикл или нет, это NP Hard и NP Complete Оба.

Найти гамильтонов цикл в графе G = (V, E), в котором V делится на 3, тоже NP Hard.
Тест на этот вопрос

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

ВОРОТА | GATE-CS-2006 | Вопрос 31

0.00 (0%) 0 votes