Uma empresa de comunicações está implantando uma rede de fibra ótica conectando 6 pontos. A figura abaixo ilustra as localizações destes pontos e apresenta as distâncias, em quilômetros, entre os pontos. Utilizando o algoritmo de Kruskal, determine qual o menor total necessário de cabos de fibra ótica para conectar todos os pontos.

Alternativa D - 149

Resolução Detalhada

O problema solicita o uso do Algoritmo de Kruskal para encontrar a Árvore Geradora Mínima (AGM). O objetivo é conectar todos os pontos (vértices) usando a menor quantidade total de cabo (peso das arestas), sem formar ciclos.

Para um grafo com 6 pontos (V=6), precisamos selecionar exatamente V - 1 = 5 arestas.

Passo 1: Ordenar as arestas por peso

Listamos todas as conexões disponíveis em ordem crescente de distância (quilômetros):

Passo 2: Selecionar as arestas

Selecionamos as arestas uma a uma, ignorando aquelas que criam um ciclo (conexão redundante entre nós já conectados).

1. Seleciona D-F (23): Conecta D e F. Total: 23.
2. Seleciona C-D (27): Conecta C ao grupo {D, F}. Total: 23 + 27 = 50.
3. Seleciona A-C (28): Conecta A ao grupo {C, D, F}. Total: 50 + 28 = 78.
4. Seleciona A-B (30): Conecta B ao grupo {A, C, D, F}. Total: 78 + 30 = 108.
5. Verifica B-C (40): Os nós B e C já estão conectados através de A (caminho B-A-C). Criaria um ciclo. Ignora.
6. Seleciona D-E (41): Conecta o nó isolado E ao grupo principal via D. Total: 108 + 41 = 149.

Neste momento, temos 5 arestas selecionadas e todos os 6 pontos estão conectados. O algoritmo termina.

Conclusão

A soma total das distâncias selecionadas é:
23 + 27 + 28 + 30 + 41 = 149

Portanto, o menor total necessário é 149 km, correspondendo à Alternativa D.