Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — Gama Consult 2024
Algoritmos e Estrutura de Dados›Estrutura de Dados
Código
qg202004
Banca
Gama Consult
Órgão
Câmara de Alto Paraíso - RO
Ano
2024
Nível
Superior
Cargo
Gestor de Tecnologia da Informação
A Teoria dos Grafos é uma área da matemática aplicada amplamente utilizada em várias disciplinas de informática e gestão. Considere os conceitos de grafos, caminhos mínimos e algoritmos de otimização. Qual das seguintes afirmações é correta em relação ao uso da matemática em algoritmos de grafos?
AO algoritmo de Dijkstra pode encontrar o caminho mínimo em grafos com arestas de pesos negativos.
BO algoritmo de Prim é utilizado para encontrar a árvore geradora mínima de um grafo ponderado e conexo.
CO algoritmo de Bellman-Ford é incapaz de detectar ciclos negativos em um grafo.
DO problema do Caixeiro Viajante (TSP) pode ser resolvido em tempo polinomial utilizando um algoritmo guloso.
Revelar gabarito e comentário▾
GabaritoB — O algoritmo de Prim é utilizado para encontrar a árvore geradora mínima de um grafo ponderado e conexo.
Comentário gerado por IA. É um apoio ao estudo, ancorado em fontes, mas pode conter imprecisões — confira sempre na fonte oficial (lei, súmula, edital e gabarito da banca). Encontrou um erro? Use “Reportar”.
Algoritmos de Grafos
Gabarito: letra B. O algoritmo de Prim é o algoritmo clássico para encontrar a árvore geradora mínima (AGM) de um grafo ponderado e conexo, funcionando corretamente com arestas de peso não negativo (e também com pesos negativos, desde que o grafo seja conexo). As demais alternativas contêm erros conceituais: Dijkstra não lida com pesos negativos; Bellman-Ford detecta ciclos negativos; e o Problema do Caixeiro Viajante (TSP) é NP-difícil, sem solução polinomial exata conhecida.
NÃO CAIA NESSA!
A banca explora a confusão clássica entre Dijkstra (que requer pesos não negativos) e Bellman-Ford (que aceita pesos negativos e detecta ciclos). Muitos candidatos pensam que Dijkstra funciona com negativos, mas o algoritmo falha nesse caso. O mesmo vale para a crença de que Bellman-Ford não detecta ciclos – ele detecta sim, e essa é uma de suas principais vantagens.
Algoritmos de grafos
1Caminho mínimo
Dijkstra
Apenas pesos não negativos
Bellman-Ford
Aceita pesos negativos
Detecta ciclos negativos
2Árvore geradora mínima
Prim
Grafo ponderado e conexo
Algoritmo guloso
3Problema NP-difícil
Caixeiro Viajante (TSP)
Sem solução polinomial exata
Aproximação gulosa possível
LEVEL · soulevel.com.br
Alternativa A — ❌ Incorreta
O algoritmo de Dijkstra não pode encontrar o caminho mínimo em grafos com arestas de pesos negativos. Ele supõe que todas as arestas têm peso não negativo, e a presença de pesos negativos pode levar a resultados incorretos, pois o algoritmo não reavalia vértices já processados. O algoritmo adequado para pesos negativos é o Bellman-Ford.
Alternativa B — ✅ Correta ⟵ GABARITO
O algoritmo de Prim é utilizado para encontrar a árvore geradora mínima (MST) de um grafo ponderado e conexo. Ele constrói a MST incrementalmente, adicionando arestas de menor peso que conectam a árvore a um novo vértice. É um algoritmo guloso clássico e correto.
Alternativa C — ❌ Incorreta
O algoritmo de Bellman-Ford é capaz de detectar ciclos negativos em um grafo. Após executar |V|-1 relaxamentos, ele realiza uma verificação adicional: se alguma aresta ainda puder ser relaxada, existe um ciclo negativo alcançável a partir da fonte. Portanto, a afirmação de que ele é incapaz é falsa.
Alternativa D — ❌ Incorreta
O Problema do Caixeiro Viajante (TSP) é um problema NP-difícil, e não se conhece um algoritmo que o resolva em tempo polinomial (a menos que P = NP). Algoritmos gulosos podem fornecer soluções aproximadas, mas não garantem a solução ótima em tempo polinomial. Portanto, a afirmação é falsa.