Numa das alas do Centro Comercial Futuro existem 8 pontos de vigilância, designados A, B, C, D, E, F, G e H, nos quais estão instaladas câmaras de vigilância.
Pretende-se encontrar a solução mais económica para a substituição das ligações internas entre as câmaras.
A Tabela 2 apresenta o comprimento, em metros, das ligações existentes entre os pontos de vigilância.

Tabela 2

De modo a minimizar os custos da intervenção, construiu-se um grafo, adotando-se o procedimento seguinte:

• seleciona-se a ligação de menor comprimento (se houver mais do que uma, escolhe-se ao acaso uma delas);
• em seguida, seleciona-se, de entre as ligações restantes, a de menor comprimento, desde que esta não leve à formação de um ciclo;
• termina-se quando todos os pontos de vigilância pertencerem a alguma das ligações selecionadas no grafo.

Admita que a substituição de cada metro de ligação interna tem o custo de 12 euros.

Determine o custo total da substituição.

Na sua resposta, apresente o grafo que resulta da aplicação do método descrito.