Questão 6: o enunciado do problema do caixeiro viajante é um problema np-completo o enunciado que empregamos atualmente foi proposto na década de 1...
Questão 6: o enunciado do problema do caixeiro viajante é um problema np-completo o enunciado que empregamos atualmente foi proposto na década de 1930 “como percorrer uma série de cidades visitando cada uma delas uma única vez e retornando para a cidade de origem de forma a otimizar o trajeto percorrendo a menor distância entre elas?” O nome desse problema deriva dos caixeiros viajantes vendedores ambulantes que percorriam diversas cidades vendendo seus produtos a resolução desse problema envolve a resolução de outro problema np-completo que inclui grafos. Qual é esse outro problema? A) Determinar se um grafo é euleriano. B) Determinar se um grafo é hamiltoniano. C) Determinar se um grafo é completo. D) Determinar se um grafo é conexo. E) Determinar se um grafo possui uma árvore geradora mínima.
O outro problema NP-completo que envolve grafos e é necessário para a resolução do problema do caixeiro viajante é determinar se um grafo é hamiltoniano.
0
0
Faça como milhares de estudantes: teste grátis o Passei Direto
Compartilhar