Determine a árvore mínima que conecta todos os nós do seguinte grafo.

Alternativa A

Para encontrar a Árvore Geradora Mínima (Minimum Spanning Tree - MST), precisamos selecionar o conjunto de arestas que conecta todos os vértices do grafo com o menor custo total possível, sem formar ciclos fechados. O método mais comum para isso é o Algoritmo de Kruskal, que ordena as arestas por peso crescente e as adiciona sequencialmente.

Análise Detalhada

Primeiro, listamos todas as arestas do grafo e seus respectivos pesos em ordem crescente:

Agora, aplicamos a seleção passo a passo:

1. Selecionar B-D (Peso 10): É a aresta mais barata. Conecta B e D.
2. Selecionar D-E (Peso 11): É a próxima mais barata. Conecta E ao grupo {B, D}.
3. Selecionar C-E (Peso 12): Conecta C ao grupo {B, D, E}.

• Atenção: A aresta C-D (peso 13) não seria selecionada agora, pois conectaria C e D já existentes no mesmo grupo, formando um ciclo (C-E-D-C).

1. Selecionar A-B (Peso 14): Conecta o nó isolado A ao resto da árvore através de B.

• Observação: A aresta A-C (peso 15) também conectaria A, mas como 14 < 15, escolhemos A-B para manter o custo mínimo.

Ao final, temos 4 arestas (número de nós - 1) conectando todos os 5 nós (A, B, C, D, E).

O conjunto de arestas formado é:

• A-B
• B-D
• D-E
• E-C (mesma coisa que C-E)

Somando os pesos: $14 + 10 + 11 + 12 = 47$.

Comparando com as outras opções:

• Opção B: Inclui D-A (22), o que aumenta muito o custo total.
• Opção C: Troca A-B (14) por A-C (15), aumentando o custo para 48.
• Opção D: Inclui A-C (15) além de outras arestas, resultando em custo superior.

Portanto, a combinação apresentada na alternativa A é a única que forma uma árvore mínima válida.