Em um grafo conexo com pesos nas arestas, qual propriedade caracteriza uma árvore geradora mínima (MST)?
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Identificar as principais formas de organizar e representar a informação de maneira estruturada (matrizes, registros, listas e grafos) ou não estruturada (números, palavras, valores verdade).
Fonte: Base Nacional Comum Curricular (MEC).Questão
Em um grafo conexo com pesos nas arestas, qual propriedade caracteriza uma árvore geradora mínima (MST)?
- A) É a árvore que conecta todos os vértices com a soma total mínima dos pesos das arestas.
- B) A soma dos pesos das arestas na MST deve ser igual ao número de vértices.
- C) Uma árvore geradora mínima tem que ser um ciclo para ser considerada válida.
- D) MST não precisa conectar todos os vértices, apenas os de menor peso.
- E) Uma MST deve conter apenas as arestas de menor peso individual, independentemente da conexão.
✅ Resposta correta: alternativa A
Resolução passo a passo
- Em um grafo conexo com n vértices, uma árvore geradora é um subgrafo que conecta todos os vértices, não possui ciclos e, portanto, tem exatamente n-1 arestas. Passo 2: Como um grafo conexo pode ter várias árvores geradoras, a árvore geradora mínima (MST) é aquela cuja soma total dos pesos das arestas é a menor possível entre todas elas. Passo 3: Por isso a alternativa A está correta, pois descreve exatamente essa propriedade: conectar todos os vértices com soma mínima dos pesos. Passo 4: A alternativa B está errada, porque a soma dos pesos depende dos valores das arestas e não do número de vértices; o número de vértices define apenas a quantidade de arestas (n-1). Passo 5: A alternativa C está errada, pois uma árvore, por definição, não contém ciclos; ter ciclo a tornaria inválida. Passo 6: A alternativa D está errada, porque a MST precisa obrigatoriamente conectar todos os vértices do grafo, caso contrário não seria uma árvore geradora. Passo 7: A alternativa E está errada, pois pegar apenas as arestas individualmente mais leves pode criar ciclos ou deixar vértices desconectados; a MST é um conjunto que conecta tudo e minimiza a soma, o que é diferente de minimizar cada aresta isoladamente. Passo 8: O gabarito oficial A está correto e coincide com a resolução feita por conta própria.
💡 Dica: Reveja as propriedades das árvores geradoras mínimas.
Alternativa por alternativa
Por definição, entre todas as árvores que alcançam todos os vértices, a MST tem o menor custo agregado das arestas, otimizando recursos em aplicações de redes e infraestrutura.
O aluno confunde o número de arestas da árvore (n-1) com a soma dos pesos, supondo que a soma deve igualar a quantidade de vértices.
Por que engana: Confundir a definição de árvore geradora mínima com a de um ciclo, acreditando que uma MST pode ser um ciclo.
O aluno acredita que a árvore geradora mínima precisa formar um ciclo, invertendo a definição de árvore, que é justamente um grafo acíclico.
O aluno pensa que a MST pode deixar vértices de fora, bastando escolher as arestas de menor peso, sem considerar que a árvore geradora deve cobrir todos os vértices.
O aluno acredita que basta escolher as arestas mais leves isoladamente, ignorando que isso pode formar ciclos ou desconectar o grafo.
Raio-X da questão
árvore geradora mínima
avaliacao
propriedades de grafos · árvores e ciclos em grafos
Estudar as propriedades das árvores geradoras mínimas em grafos.
Confundir a definição de árvore geradora mínima com a de um ciclo, acreditando que uma MST pode ser um ciclo.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Para que o algoritmo de Dijkstra retorne corretamente caminhos mínimos em um grafo (dirigido ou não) com pesos nas…
- Projete um algoritmo (pseudocódigo) baseado em Kruskal ou Prim que, dado um grafo conectado ponderado (dados: lista de…
- Dado um grafo simples não direcionado com V vértices e E arestas, qual condição necessária e suficiente (usando V, E e…
- Qual é a principal característica dos grafos na resolução de problemas de caminhos?
- Escolha a alternativa que melhor define um grafo ponderado.
- Qual propriedade deve ter um grafo dirigido para que seja possível executar um algoritmo de ordenação topológica sobre…
Todas as questões de Programação - Programação usando grafos e árvores
🔎 Procurar outra questão
Procure no banco do GeraProva pelo tema ou por um trecho do enunciado. Cada questão já vem com resolução comentada e a análise de cada alternativa.
Professor: monte a prova com questões como esta, com gabarito e folha de respostas, em 30 segundos. Ver planos · Blog