Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — FUNCERN 2025
Algoritmos e Estrutura de Dados›Estrutura de Dados
Código
qg465623
Banca
FUNCERN
Órgão
IF-PE
Ano
2025
Nível
Superior
Cargo
Analista de Tecnologia da Informação - Área Desenvolvimento
Em um grafo ponderado, não-direcionado, conexo com n vértices, a árvore geradora mínima (MST) possui sempre
Aas n arestas de menor peso do grafo que não formam ciclo.
Bn+1 arestas e o menor caminho entre qualquer par de vértices na árvore.
Ca garantia de excluir a aresta de maior peso do grafo original, independentemente da quantidade de arestas.
Do mesmo número de arestas que o grafo original, com a garantia de menor caminho entre qualquer par de vértices na árvore.
En-1 arestas, cuja soma dos pesos das arestas é a menor possível.
Revelar gabarito e comentário▾
GabaritoE — n-1 arestas, cuja soma dos pesos das arestas é a menor possível.
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”.
Árvore Geradora Mínima (MST) – Propriedades
Gabarito: letra E. A Minimum Spanning Tree (MST) de um grafo ponderado, não‑direcionado e conexo com (n) vértices possui exatamente {{n-1 arestas}} e a soma dos pesos dessas arestas é {{a menor possível}} entre todas as árvores geradoras do grafo. Essa é a definição fundamental do conceito.
A questão testa principalmente duas propriedades: o número de arestas de uma árvore em um grafo com (n) vértices (sempre (n-1)) e o objetivo de minimização do peso total (não a garantia de caminhos mínimos entre pares de vértices).
Alternativa A — ❌ Incorreta
Afirma que a MST contém as (n) arestas de menor peso que não formam ciclo. Dois erros: (1) uma árvore tem (n-1) arestas, não (n); (2) a MST não é simplesmente o conjunto das arestas mais leves – ela deve conectar todos os vértices sem ciclos, podendo incluir arestas que não estão entre as (n) mais leves.
Alternativa B — ❌ Incorreta
Apresenta (n+1) arestas (qualquer árvore tem (n-1)) e afirma que a MST garante o menor caminho entre qualquer par de vértices. Isso é propriedade de uma árvore de caminhos mínimos (Shortest Path Tree), não da MST.
Alternativa C — ❌ Incorreta
Diz que a MST sempre exclui a aresta de maior peso do grafo original. Não há tal garantia: se o grafo tiver apenas um ciclo, a MST conterá a aresta mais pesada, desde que ela não seja a única formadora de ciclo. A MST escolhe o conjunto de arestas que minimiza a soma total, podendo incluir a maior aresta se necessário.
Alternativa D — ❌ Incorreta
Compara o número de arestas da MST com o do grafo original (que pode ter muitas arestas). A MST sempre tem (n-1) arestas, independente da densidade do grafo. Além disso, repete o erro de associar MST a caminho mínimo.
Alternativa E — ✅ Correta ⟵ GABARITO
“(n-1) arestas, cuja soma dos pesos das arestas é a menor possível.” Essa é a definição exata de Minimum Spanning Tree: uma árvore geradora (conecta todos os vértices, sem ciclos, com (n-1) arestas) que minimiza a soma dos pesos.
NÃO CAIA NESSA!
A banca explora duas confusões comuns: (1) trocar o número de arestas da árvore ((n-1)) por (n) ou (n+1); (2) confundir MST (minimiza soma total das arestas) com árvore de caminhos mínimos (minimiza distância entre um par específico). Fique atento: toda MST é uma árvore, mas nem toda árvore é MST – e ela não tem relação com caminhos mínimos entre vértices.
Gabarito: letra E – correta a definição clássica de MST.