Grafos: Calcular Percurso de Prova de Trail (MACS 11º ano)

A equipa organizadora de uma prova de trail pretende definir um percurso que passe, obrigatoriamente, pelos cinco postos de controlo:
C1, C2, C3, C4 e C5.
Na Tabela 4, estão registadas as distâncias mínimas, em metros, entre cada dois postos de controlo.
Tabela 4

	C1	C2	C3	C4	C5
C1		2770	2400	2260	1780
C2	2770		2370	2360	2550
C3	2400	2370		2225	2660
C4	2260	2360	2225		3100
C5	1780	2550	2660	3100

A equipa organizadora decidiu que a prova teria início no posto de controlo C2 e terminaria num dos restantes postos de controlo.
Para definir o percurso, a equipa optou por aplicar o método a seguir descrito.

• Seleciona-se o posto de controlo seguinte, tendo em conta que:
deve ser o mais próximo possível; se houver dois postos à mesma distância, a seleção é aleatória.

• Procede-se como foi indicado no ponto anterior, não se repetindo nenhum posto de controlo, e terminando após a passagem por todos os postos de controlo.
Determine o comprimento do percurso da prova, respeitando as condições definidas pela equipa organizadora.
Na sua resposta, apresente:
um grafo que resulte da aplicação do método descrito; a ordem de passagem pelos postos de controlo.

Apresentar um grafo com as arestas selecionadas 12 pontos Identificar os vértices 2 pontos Desenhar as arestas 10 pontos Determinar o comprimento do percurso da prova (8765 m) 4 pontos Apresentar a ordem de passagem pelos postos de controlo 3 pontos [C2-C4-C3 – C1 – C5]