Mariana decidiu viajar até Praga e, a partir daí, visitar outras capitais europeias, regressando a essa primeira cidade no final da visita.

As capitais que pretende visitar, além de Praga, são Berlim, Bratislava, Varsóvia e Viena.

Para planear as suas férias, Mariana utilizou a Tabela 3, que apresenta as distâncias, em quilómetros, entre as referidas capitais.

Tabela 3

Com base na informação apresentada e num mapa da Europa semelhante ao que se apresenta na Figura 1, Mariana construiu um grafo em que duas capitais são interligadas, desde que os países a que pertencem façam fronteira entre si.

O seu percurso será definido a partir do grafo construído 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 por Mariana, com início e fim em Praga.

Na sua resposta, apresente:

• um grafo semelhante ao que Mariana construiu;
• a ordenação das arestas selecionadas pelo algoritmo descrito;
• um percurso que Mariana poderá ter definido.