Dois conhecidos problemas de pesquisa operacional possuem uma ampla gama de aplicações em comunicação

Dois conhecidos problemas de pesquisa operacional possuem uma ampla gama de aplicações em comunicação

ENADE 2014 - QUESTÃO 22

Dois conhecidos problemas de pesquisa operacional possuem uma ampla gama de aplicações em comunicação, transporte e planejamento: o problema do carteiro chinês (PCC), e o problema do caixeiro viajante (PCV). O primeiro consiste em minimizar o esforço de um carteiro que precisa percorrer todas as ruas de uma cidade. O segundo consiste em minimizar o deslocamento do vendedor que precisa visitar todas as cidades interconectadas de uma dada região, retornando à cidade de origem. Esses problemas têm sido modelados com teoria dos grafos, de onde se destacam dois conceitos relacionados: circuito euleriano e ciclo hamiltoniano.

Uma trilha é uma sequência de arestas adjacentes em que não há repetição de arestas, e seu comprimento é a quantidade de arestas. A trilha é dita fechada se inicia e finaliza no mesmo vértice. Assim, um grafo com m arestas é euleriano se nele existe uma trilha fechada de comprimento m (trilha euleriana). Um ciclo hamiltoniano é uma trilha fechada que passa sem repetir por todos os vértices.

Com base nos conceitos acima, avalie as afirmações a seguir.

I. Se o grafo das cidades e suas interconexões for euleriano, então o PCV pode ser resolvido de uma forma tal que o caixeiro não terá que fazer visitas repetidas,

II. Se todas as cidades se conectam com todas as outras, então a solução do PCV é um ciclo hamiltoniano correspondente ao menor deslocamento.

III. Se o grafo for euleriano e possuir um ciclo hamiltoniano, então o PCC e o PCV darão como resultado a mesma trilha.

É correto o que se afirma em

A) II, apenas.

B) III, apenas.

C) I e II, apenas.

D) I e III, apenas.

E) I, II e III.

RESOLUÇÃO:

Não temos resolução para essa questão! Você sabe explicar? Copie o link dessa página e envie sua resolução clicando AQUI!

GABARITO:

 A) II, apenas.

QUESTÃO DISPONÍVEL EM:

- Prova Engenharia de Computação ENADE 2014 com Gabarito