Num campus universitário, pretende-se instalar uma iluminação decorativa, constituída por um fio de luzes suspenso entre seis edifícios, E1, E2, E3, E4, E5 e E6.

A Tabela 3 apresenta o comprimento previsto, em metros, do fio de luzes que seria necessário instalar entre cada par de edifícios.

Tabela 3

De modo a minimizar o custo da instalação da iluminação decorativa, construiu-se um grafo que resulta do método que a seguir se descreve.

• Escolhe-se, ao acaso, um dos seis edifícios e, de seguida, de entre os restantes, seleciona-se aquele que, por se encontrar a uma menor distância do primeiro, implique um menor comprimento do fio de luzes previsto.
• Seleciona-se outro edifício que ainda não tenha sido escolhido e que, por se encontrar a uma menor distância dos edifícios anteriormente escolhidos, implique um menor comprimento do fio de luzes previsto.
• Repete-se o ponto anterior até todos os edifícios terem sido selecionados.

Admita que a instalação da iluminação decorativa terá um custo de 3,5 euros por cada metro de fio de luzes previsto.

Determine o custo total desta instalação.

Na sua resposta, apresente:

• um grafo ponderado que resulte da aplicação do método descrito;
• o comprimento mínimo previsto, em metros, do fio de luzes a instalar.