Uma classe de problemas NP utiliza algoritmos determinísticos em tempo polinomial para verificar se uma solução pode ser válida para determinado pr...

A alternativa correta é a letra C) I e III estão corretas. Justificativa: I. No ciclo hamiltoniano, o objetivo é encontrar um ciclo que passe por todos os vértices de um grafo exatamente uma vez. II. O problema do caixeiro viajante busca uma rota para as cidades em determinado conjunto C que passe por todas as cidades exatamente uma vez e que minimize a distância total percorrida. III. Em um grafo, os vértices precisam ter diferentes cores para que o problema de coloração de grafos seja válido. IV. O problema da mochila booleana tenta achar um valor máximo de objetos para colocar na mochila sem violar a capacidade desta, considerando que cada objeto pode ser escolhido ou não para ser colocado na mochila. Portanto, as afirmações I e III estão corretas. A afirmação II está incorreta, pois o objetivo do problema do caixeiro viajante é minimizar a distância total percorrida, não maximizá-la. A afirmação IV também está incorreta, pois o problema da mochila booleana não busca o valor máximo de objetos, mas sim a combinação de objetos que resulte no maior valor possível respeitando a capacidade da mochila.