Exercício 3 · Exame Nacional Matemática Aplicada às Ciências Sociais 2.ª fase 2023

3. 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.

1.

2.

3.

4.