Uma empresa pretende instalar cabo de fibra ótica para interligar seis departamentos: D1, D2, D3, D4, D5 e D6.

Na Tabela 4, encontram-se registadas as distâncias mínimas, em metros, que serviram de base para o projeto de instalação do cabo de fibra ótica entre os departamentos.

Tabela 4

De modo a minimizar o custo da instalação do cabo de fibra ótica, aplicou-se o método a seguir descrito.

• Escolhe-se, ao acaso, um dos seis departamentos e seleciona-se a menor das distâncias entre esse departamento e os restantes. Ficam assim escolhidos dois departamentos.
• Seleciona-se a menor das distâncias entre qualquer um dos dois departamentos escolhidos e um departamento ainda não escolhido.
• Seleciona-se a menor das distâncias entre qualquer um dos departamentos escolhidos e um departamento ainda não escolhido.
• Repete-se o ponto anterior até todos os departamentos terem sido selecionados.

Determine o comprimento mínimo, em metros, de cabo de fibra ótica que é necessário instalar.

Na sua resposta, apresente um grafo que resulte da aplicação do método descrito e que permita identificar as distâncias selecionadas.