A ParaPagar pretende renovar a rede de cabo de fibra ótica em algumas das ligações existentes entre seis postos de comunicação, P1, P2, P3, P4, P5 e P6.

Na Figura 1, apresenta-se um esquema simplificado dessas ligações, no qual se indica, junto de cada segmento de reta, o comprimento, em quilómetros, de cada ligação.

Com vista à minimização de custos, optou-se por começar a renovação no posto de comunicação P4 e aplicar o método que a seguir se descreve.

• Seleciona-se o posto seguinte, tendo em conta que:
  • deverá corresponder ao posto mais próximo;
  • se houver dois postos à mesma distância, a seleção é aleatória.
• Procede-se como foi indicado no ponto anterior, partindo do último posto selecionado, não se repetindo nenhum e terminando depois de todos os postos serem incluídos.

Determine a quantidade mínima, em quilómetros, de cabo de fibra ótica a renovar.

Na sua resposta, apresente um grafo que resulte do método descrito e que permita identificar as ligações a renovar.