Número:
Enunciado: Considere o seguinte problema como o Problema do Carteiro Idoso: deseja-se encontrar o menor circuito (a soma dos pesos de arestas seja mínimo), cuja origem é a posição inicial do carteiro, passando exatamente 1 vez em cada residência. A figura abaixo ilustra o problema, onde o carteiro e cada residência são nós de um grafo não orientado ponderado.
Dada a definição informal do problema, é correto afirmar que:
a. Este problema é da classe NPC, pois é possível associá-lo ao problema de encontrar um circuito de Euler.
b. Este problema é da classe P, pois é possível resolvê-lo aplicando o algoritmo de Prim.
c. Este problema é da classe NPC, pois é possível associá-lo ao problema de encontrar um ciclo Hamiltoniano.
d. Este problema é da classe P, pois é possível resolvê-lo aplicando o algoritmo de Dijkstra.
e. NDA
Ideia Original: Wallace Felipe Francisco Cardoso
Nenhum comentário:
Postar um comentário