Alternativa correta: E - As afirmações I, II e III são corretas.

1. Tema central:

Esta questão aborda algoritmos clássicos de grafos, fundamentais em concursos de TI e Engenharia. Conhecimentos sobre ordenação topológica, árvore geradora mínima e caminho mínimo são essenciais.

2. Resumo teórico:

• Ordenação topológica: só é possível em grafos dirigidos acíclicos (DAGs). Se há ciclo, a ordenação não pode ser feita. (Cormen et al., 2012)
• Algoritmo de Kruskal: encontra a árvore geradora mínima em grafos conexos, unindo os vértices com as menores arestas sem formar ciclos.
• Dijkstra: calcula caminhos mínimos desde um vértice, mas requer que todos os pesos sejam não-negativos, pois com pesos negativos pode dar resposta errada.

3. Justificativa da alternativa correta:

I – Correta. De acordo com Cormen, não há ordenação topológica possível em grafos com ciclo.

II – Correta. Kruskal realmente encontra a árvore geradora mínima (Minimum Spanning Tree), conectando todos os vértices com o menor custo total.

III – Correta. O algoritmo de Dijkstra pressupõe que todos os pesos das arestas são não-negativos, pois com pesos negativos ele pode errar.

4. Análise das alternativas incorretas:

• A: Somente a I? Errado, pois II e III também são corretas.
• B: Apenas I e II? Incorreto, pois III também está correta.
• C: Só II? Falso, pois I e III também são corretas.
• D: Apenas II e III? Falso, pois I também está correta.

5. Estratégias de resolução:

Leia atentamente as afirmações e destaque palavras-chave (ciclo, mínima, não negativos). Procure lembrar do algoritmo em sua essência. Cuidado com pegadinhas como “nenhuma” ou “todos”, que requerem atenção total ao conceito original.

Referência:

CORMEN, Thomas H. Algoritmos: Teoria e Prática. 3ª Ed. Rio de Janeiro: Elsevier, 2012.

Gostou do comentário? Deixe sua avaliação aqui embaixo!