Considere as seguintes asserções e seguidamente assinale a alternativa correta. I. O problema do Circuito Hamiltoniano corresponde a verificar se e...

A alternativa correta é: I, II e III. A afirmação I está correta, pois o problema do Circuito Hamiltoniano consiste em encontrar um circuito que passe por todos os vértices de um grafo exatamente uma vez. A afirmação II também está correta, pois encontrar um caminho Hamiltoniano em um grafo é um problema NP-completo, o que significa que não há um algoritmo conhecido que possa resolver o problema de forma eficiente para todos os casos. A afirmação III está incorreta, pois o algoritmo conhecido para resolver o problema do circuito Hamiltoniano é O(n² * 2^n), que é mais eficiente do que O(n!).