A Elsa, que em 2018 fez um Interrail, relatou à Maria a sua viagem, explicando-lhe também algumas dificuldades na sua organização.

Uma das dificuldades foi decidir que países visitariam e, em cada país, a quantas cidades iriam.

O grupo de amigos da Elsa acabou por decidir que visitariam a Alemanha, a Áustria, a França, a Itália e a Suíça e que, em cada país, iriam apenas a uma cidade.

Na Tabela 2, apresentam-se as distâncias, em quilómetros, entre as cidades que o grupo considerou mais atrativas e os países a que pertencem.

Tabela 2

Os amigos acordaram que o percurso a realizar seria definido partindo de um grafo no qual duas cidades são interligadas se não pertencerem ao mesmo país, selecionando-se apenas uma cidade de cada país e atendendo ao seguinte algoritmo:

• escolher a aresta do grafo com menor peso, qualquer que ela seja;
• escolher, sucessivamente, as arestas de menor 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.

Apresente um percurso possível, definido pelo grupo de amigos da Elsa, com início e fim na cidade de Paris.

Na sua resposta, apresente:

• a ordenação das arestas selecionadas pelo algoritmo descrito;
• um grafo que resulte da aplicação do algoritmo;
• um percurso que o grupo de amigos da Elsa poderá ter definido.