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

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.