Resolução da Questão de Otimização de Redes
Esta questão trata do clássico problema de Árvore Geradora Mínima (Minimum Spanning Tree), comum em logística, redes de telecomunicações e infraestrutura. O objetivo é conectar todos os pontos (vértices) utilizando o menor custo total possível, sem formar ciclos (circuitos fechados).
1. Entendendo o Problema
Para minimizar o custo da instalação da rede elétrica, devemos selecionar as ligações (arestas) com os menores valores numéricos, garantindo que todas as tomadas (A, B, C, D, E, F) fiquem conectadas umas às outras.
2. Aplicação do Algoritmo (Método de Kruskal)
Uma forma didática de resolver é ordenar as distâncias disponíveis do menor para o maior e ir escolhendo-as, desde que não fechem um círculo.
Lista de distâncias ordenadas:
- 8 m: Ligação B-D e Ligação D-E
- 9 m: Ligação B-E
- 10 m: Ligação A-C
- 11 m: Ligação D-F
- 12 m: Ligação A-B e Ligação C-E
- 13 m: Ligação B-F
- 14 m: Ligação C-D
- 17 m: Ligação E-F
Passo a passo da seleção:
- Escolha 8m (B-D): Conectamos B e D.
- Escolha 8m (D-E): Conectamos E ao grupo B-D. (Nós conectados: B, D, E).
- Escolha 9m (B-E): Descartada. Se escolhermos, formamos um triângulo B-D-E-B, criando um ciclo desnecessário e aumentando o custo.
- Escolha 10m (A-C): Conectamos A e C. (Novo grupo isolado: A, C).
- Escolha 11m (D-F): Conectamos F ao grupo principal (B, D, E). (Grupo principal: B, D, E, F).
- Conexão final: Precisamos unir o grupo {A, C} ao grupo {B, D, E, F}.
- As opções com menor custo são A-B (12) ou C-E (12).
- Ambas geram o mesmo custo total. A alternativa apresentada utiliza a ligação C-E.
## Análise das Alternativas
| Alternativa | Ligações Selecionadas | Custos Somados | Viável? |
|---|
| A | A-C (10) + B-D (8) + C-E (12) + D-E (8) + D-F (11) | 49 | Sim (Menor custo, sem ciclos) |
| B | A-B (12) + B-D (8) + C-D (14) + D-E (8) + D-F (11) | 53 | Não (Inclui aresta cara C-D) |
| C | A-C (10) + B-E (9) + C-E (12) + D-F (11) + E-F (17) | 59 | Não (Inclui aresta cara E-F e cria ciclos) |
| D | A-B (12) + B-C (?) + C-E (12) + D-E (8) + E-F (17) | > 50 | Não (Inclui aresta cara E-F) |
Conclusão
A combinação de ligações que resulta no menor custo total (49 metros) e conecta todos os pontos sem redundância é a listada na alternativa A.
Alternativa A