MACS 11º Ano | Grafos: Itinerário Ótimo e Minimização de Tempo (2023)

Os pais da Luísa fizeram um cruzeiro com o itinerário seguinte.
Dia 1 – Atenas (A) Dia 2 – Istambul (I) Dia 3 – Volos (V) Dia 4 – Mykonos (M) Dia 5 - Rodes (R) Dia 6 - Santorini (S) Dia 7 – Atenas (A).
A Luísa, não podendo acompanhar os pais, tenciona visitar os mesmos locais, sem repetir nenhum deles, mas viajando em transportes públicos terrestres e marítimos.
No seu planeamento, a Luísa pretende iniciar e terminar a viagem em Atenas, despendendo o menor tempo possível nas deslocações entre estes locais.
Na Tabela 1, estão registadas as durações das viagens entre os vários locais a visitar, pesquisadas na Internet pela Luísa.
Tabela 1:

	A	I	M	R	S	V
A		17h20	2h50	15h50	9h30	4h40
I	17h20		26h00	15h30	28h20	14h50
M	2h50	26h00		10h30	2h30	6h10
R	15h50	15h30	10h30		2h40	7h00
S	9h30	28h20	2h30	2h40		6h20
V	4h40	14h50	6h10	7h00	6h20

.
Para definir o seu percurso, a Luísa decide construir um grafo para modelar a situação, aplicando o método seguinte.

• Escolhe-se a aresta do grafo com menor peso, qualquer que ela seja.

• Escolhe-se, sucessivamente, as arestas com menor peso, garantindo que três arestas do grafo que está a ser definido não se encontram num mesmo vértice e não permitindo a formação de quaisquer percursos fechados que não incluam todos os vértices.
Poderá a Luísa visitar os locais pela mesma ordem seguida pelos pais? Na sua resposta, apresente:
– a ordenação das arestas selecionadas que resulte da aplicação do método descrito; – um grafo semelhante ao que terá sido construído pela Luísa; – um possível itinerário definido pela Luísa.

Apresentar a ordenação das arestas selecionadas 6 pontos Apresentar um grafo que modele a situação 8 pontos Associar os vértices aos locais a visitar 2 pontos Associar as arestas à duração das viagens 6 pontos Apresentar um itinerário possível 3 pontos [Por exemplo: A-M-S-R-I-V-A] Concluir 3 pontos [A Luísa não poderá visitar os locais pela mesma ordem seguida pelos pais.]