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 esses problemas, analise as seguintes afirmações: I. O 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, devemos comparar cada afirmativa com as definições técnicas padrão dos problemas de otimização combinatória listados.

Análise Detalhada

Abaixo, analisamos cada uma das quatro proposições apresentadas no enunciado:

• I. Falsa (Ciclo Hamiltoniano):
  A definição correta de um Ciclo Hamiltoniano é um caminho fechado que passa por todos os vértices exatamente uma vez. A afirmativa diz "independentemente do número de vezes", o que permitiria passar pelos vértices múltiplas vezes. Isso contradiz a definição estrita do problema.
• II. Falsa (Caixeiro Viajante):
  O objetivo clássico do Caixeiro Viajante é encontrar a rota com a menor distância possível (minimização). Na sua versão de decisão em teoria da complexidade, pergunta-se se existe uma rota com custo menor ou igual a $k$, e não maior ou igual.
• III. Verdadeira (Coloração de Grafos):
  O problema consiste em atribuir cores aos vértices de modo que nenhum par de vértices adjacentes tenha a mesma cor. Embora a frase diga apenas "vértices precisam ter diferentes cores", ela descreve corretamente a regra de restrição principal (conflito de cores entre vizinhos) necessária para validar a coloração.
• IV. Verdadeira (Mochila Booleana):
  Esta afirmativa descreve perfeitamente o Problema da Mochila (Knapsack). O objetivo é selecionar um subconjunto de itens para maximizar o valor total sem ultrapassar a capacidade máxima de peso definida.

Conclusão

Pela análise acima:

• Afirmativas I e II estão incorretas.
• Afirmativas III e IV estão corretas.

Portanto, a única alternativa que contém apenas as afirmações verdadeiras é a C.