Pular para o conteúdo principal

Questão de Algoritmos e Estrutura de Dados — Grafos — FGV 2024

Algoritmos e Estrutura de DadosGrafos
Código
fg077432
Banca
FGV
Órgão
CVM
Ano
2024
Nível
Superior
Cargo
Analista - Perfil 9 - TI / Infraestrutura e Segurança - Tarde
Considere uma árvore que contém todo e qualquer nó em um grafo, mais formalmente, uma spanning tree de um grafo G = (N, E) e um grafo G' = (N, E') tal que E' é um subconjunto de E, G' é conectado, G' não contém nenhum ciclo e G' contém todos os nós originais em G.Se cada enlace tiver um custo associado e o custo de uma árvore for a soma dos custos dos enlaces, é correto afirmar que uma árvore cujo custo seja o mínimo entre todas as spanning trees é denominada:
  1. Aspanning tree mínima;
  2. Bspanning tree máxima;
  3. Cspanning tree de diâmetro mínimo;
  4. Dspanning tree de diâmetro máximo;
  5. Espanning tree geradora de caminho máximo.
Revelar gabarito e comentário

GabaritoA — spanning tree mínima;

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”.

Árvores Geradoras Mínimas (Minimum Spanning Tree)

Gabarito: letra A. A definição de spanning tree (árvore geradora) com custo mínimo entre todas as árvores geradoras possíveis é exatamente o conceito de árvore geradora mínima ou minimum spanning tree. O enunciado descreve a estrutura e pede o nome quando se minimiza o custo total das arestas.

Alternativa A — ✅ Correta ⟵ GABARITO

A alternativa corretamente denomina spanning tree mínima (ou árvore geradora mínima) a árvore que, dentre todas as spanning trees, possui o menor custo total (soma dos pesos dos enlaces). É o conceito clássico estudado em teoria dos grafos, com algoritmos como os de Kruskal e Prim.

Alternativa B — ❌ Incorreta

"Spanning tree máxima" seria o oposto: a árvore geradora de maior custo. O problema pede o custo mínimo, não o máximo.

Alternativa C — ❌ Incorreta

"Spanning tree de diâmetro mínimo" refere-se a uma árvore geradora que minimiza o diâmetro (maior distância entre dois nós), não o custo total das arestas. São objetivos diferentes.

Alternativa D — ❌ Incorreta

"Spanning tree de diâmetro máximo" também foca no diâmetro, mas maximizando-o, o que não corresponde à definição de custo mínimo.

Alternativa E — ❌ Incorreta

"Spanning tree geradora de caminho máximo" não é um termo padrão; pode confundir com o problema do caminho mais longo, mas não se relaciona com minimizar a soma dos custos das arestas.

Gabarito: letra A.

Link permanente: /questoes/fg077432