Matemática 11.º Ano (2015): Problema de Otimização de Percursos (Grafo)

Uma agência de viagens, sediada no concelho de Avelares, organiza e vende, através da Internet, percursos de autocarro entre várias cidades europeias.
Para organizar um percurso que passe por Amesterdão, Berlim, Munique, Paris e Viena, um funcionário da agência começou por registar, na Tabela 2, as distâncias mínimas, em quilómetros, entre cada duas cidades.
Tabela 2

	Amesterdão	Berlim	Munique	Paris	Viena
Amesterdão		663	825	501	1148
Berlim			604	1055	674
Munique				828	435
Paris					1236
Viena

De forma a minimizar os custos operacionais, o funcionário definiu, através de um grafo, um percurso fechado que liga as cinco cidades, tendo adotado o seguinte procedimento:

• escolher a aresta do grafo com menos peso, qualquer que ela seja;
• escolher, sucessivamente, as arestas de menos peso, garantindo que três arestas do percurso que está a ser definido não se encontram num mesmo vértice e não permitindo que se fechem percursos sem que todos os vértices sejam incluídos;
• apresentar um percurso pretendido conforme o vértice de partida escolhido.
Apresente um percurso possível, com início e fim em Amesterdão, de acordo com o procedimento utilizado pelo funcionário da agência.
Na sua resposta, apresente:
– o grafo usado, indicando os pesos de cada aresta; – um percurso que o funcionário poderá ter definido.

Apresentar um grafo com as arestas escolhidas 17 pontos Selecionar as arestas 8 pontos Identificar os vértices (ver nota) 3 pontos Desenhar as arestas (ver nota) 3 pontos Indicar as ponderações das arestas (ver nota) 3 pontos Apresentar um percurso de acordo com o pedido 3 pontos [Um percurso possível é: Amesterdão – Paris – Viena – Munique – Berlim – Amesterdão] Nota - A pontuação desta etapa não é desvalorizada caso o grafo apresentado contenha toda a informação fornecida na Tabela 2.