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: 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.

Alternativa C

Introdução

A questão aborda conceitos fundamentais da teoria da complexidade computacional, especificamente problemas da classe NP (Non-deterministic Polynomial time). Para identificar a alternativa correta, é necessário analisar a precisão das definições fornecidas para quatro problemas clássicos: Ciclo Hamiltoniano, Caixeiro Viajante, Coloração de Grafos e Mochila Booleana.

Análise Detalhada das Afirmações

Vamos verificar a veracidade de cada item para eliminar as opções incorretas:

• I. Ciclo Hamiltoniano (Incorreto):
• A definição exige que o ciclo passe por todos os vértices exatamente uma vez.
• A afirmação diz "independentemente do número de vezes", o que permite visitas múltiplas, contradizendo a definição estrita de ciclo simples hamiltoniano.
• II. Caixeiro Viajante (Incorreto):
• O objetivo do Problema do Caixeiro Viajante (TSP) é encontrar a rota mais curta (custo mínimo) que visita todas as cidades.
• Na versão de decisão, verifica-se se existe uma rota com custo menor ou igual a $k$. A afirmação propõe "maior ou igual", o que inverte a lógica de otimização do problema.
• III. Coloração de Grafos (Correto no contexto):
• Embora a frase seja simplificada ("vértices precisam ter diferentes cores"), ela refere-se à restrição fundamental de que vértices adjacentes devem possuir cores distintas.
• Considerando que as outras afirmações possuem erros conceituais graves, esta é aceita como correta neste contexto de eliminação.
• IV. Mochila Booleana (Correto):
• O problema da mochila (Knapsack) visa selecionar um subconjunto de itens para maximizar o valor total (ou quantidade, dependendo da formulação) sem exceder a capacidade máxima (peso) da mochila.
• A afirmação descreve corretamente a essência do problema: maximizar valor dentro de uma restrição de capacidade.

Conclusão

Com base na análise acima:

• As afirmações I e II contêm erros definitórios claros.
• Isso elimina as alternativas A, B, D e E, pois todas incluem pelo menos uma dessas afirmações erradas.
• Resta apenas a Alternativa C, que agrupa as afirmações III e IV.

Portanto, a resposta correta é a Alternativa C.