Uma classe de problemas NP utiliza algoritmos determinísticos em tempo polinomial para verificar se uma solução pode ser válida para determinado problema. Os problemas do ciclo hamiltoniano, do caixeiro viajante, da coloração de grafos e da mochila booleana são exemplos de problemas da classe NP. Em relação a essas afirmações, analise as seguintes afirmações: I. No ciclo hamiltoniano, o objetivo é encontrar um ciclo que passe por todos os vértices de um grafo independentemente do número de vezes que passe pelo vértice. II. Um dos problemas da classe NP caixeiro viajante busca uma rota para as cidades em determinado conjunto C cujo tamanho da rota seja maior ou igual a k. 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. Está correto o que se afirma em:

Alternativa C

Para resolver esta questão, utilizaremos a técnica de análise de afirmações e eliminação de alternativas, focando nos conceitos fundamentais de Teoria da Computação e Grafos.

Análise das Afirmações

Afirmação I: Incorreta

• Ciclo Hamiltoniano: A definição exige que o ciclo passe por todos os vértices exatamente uma vez (e retorne ao início).
• Erro na questão: A frase diz "independentemente do número de vezes", o que permitiria repetir vértices, caracterizando um circuito, mas não um ciclo hamiltoniano estrito.

Afirmação II: Incorreta

• Caixeiro Viajante (TSP): O objetivo clássico é encontrar a rota com a menor distância possível (minimização).
• Erro na questão: A afirmação sugere buscar um tamanho "maior ou igual a k". Na versão de decisão do problema (NP-Completo), pergunta-se se existe um caminho com custo menor ou igual a $k$. Buscar um caminho "maior" não é o problema de otimização padrão.

Afirmação III: Correta (no contexto da questão)

• Coloração de Grafos: A regra fundamental é que vértices adjacentes (conectados por uma aresta) devem possuir cores diferentes.
• Interpretação: Embora a frase generalize dizendo "os vértices", ela descreve a essência da restrição de validade da coloração (cores distintas para nós conectados). É a única afirmação plausível restante após eliminar I e II.

Afirmação IV: Correta

• Problema da Mochila (Knapsack): O objetivo é selecionar um conjunto de itens para maximizar o valor total (ou número, dependendo da variante) sem ultrapassar a capacidade máxima de peso da mochila.
• Validação: A descrição resume corretamente a função objetivo (maximização) e a restrição (capacidade).

Conclusão

Como as afirmações I e II estão claramente erradas, podemos descartar imediatamente as alternativas A, B, D e E.

Sobrou apenas a combinação de III e IV.

Alternativa C.