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

3. No parque de campismo de Dujal, existem cinco ecopontos: A, B, C, D e E.

No final de cada dia, um funcionário recolhe o conteúdo dos ecopontos. De modo a tornar mais eficiente o seu trabalho, o funcionário definiu um itinerário, com início e fim no portão do parque (P), para a recolha do conteúdo dos cinco ecopontos.

O itinerário definido resultou de um grafo construído com o algoritmo seguinte:

escolher a aresta do grafo com menor peso, qualquer que ela seja;

escolher, 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 que se formem quaisquer percursos fechados que não incluam todos os vértices.

As distâncias mínimas, em metros, entre cada dois ecopontos e entre o portão e cada um dos cinco ecopontos estão registadas na Tabela 2.

Tabela 2

· B · C · D · E · P

A · 310 · 730 · 365 · 600 · 395

B · · 550 · 400 · 790 · 710

C · · · 800 · 610 · 366

D · · · · 605 · 615

E · · · · · 380

Apresente um possível itinerário, definido pelo funcionário, com início e fim no portão.

Na sua resposta, apresente:

a ordenação das arestas selecionadas pelo algoritmo descrito;

um grafo semelhante ao que terá sido construído pelo funcionário.

1.

2.

3.