Dado um grafo simples não direcionado com V vértices e E arestas, qual condição necessária e suficiente…
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
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 conectividade) para que o grafo seja uma árvore?
- A) Um grafo com menos de V - 1 arestas é uma árvore.
- B) Um grafo é árvore se for desconectado e E = V - 1.
- C) Um grafo é árvore se V = 0 e E = 0.
- D) O grafo é árvore se, e somente se, for conectado e E = V - 1.
- E) Um grafo é árvore se for conectado e E = V + 1.
✅ Resposta correta: alternativa D
Resolução passo a passo
- Lembre a definição: uma árvore é um grafo simples, não direcionado, conexo e sem ciclos (acíclico).
- Um resultado clássico da teoria dos grafos diz que, em um grafo com V vértices, são equivalentes: ser árvore; ser conexo com E = V - 1; ser acíclico com E = V - 1. Portanto, para caracterizar árvore usando V, E e conectividade, basta exigir conectividade e E = V - 1.
- Verifique que a condição é necessária: toda árvore com V vértices tem exatamente V - 1 arestas, pois cada vértice além do primeiro entra ligado por uma única aresta ao restante ao ser adicionado na ordem de uma busca.
- Verifique que a condição é suficiente: um grafo conexo com V vértices e V - 1 arestas não pode conter ciclo, pois um grafo conexo com um ciclo teria mais arestas do que o necessário para conectar os vértices; logo é acíclico e conexo, ou seja, é árvore.
- Analise as alternativas. A) está errada, pois um grafo com poucas arestas pode ser desconectado (por exemplo, sem arestas), e não é árvore. B) está errada, pois exige desconexão, o que contradiz a conectividade necessária para ser árvore. C) está errada, pois o grafo vazio sem vértices não é uma árvore usual, e a condição não caracteriza árvores em geral. E) está errada, pois um grafo conexo com V + 1 arestas tem obrigatoriamente um ciclo.
- Conclusão: a alternativa correta é a D, que coincide com o gabarito oficial.
💡 Dica: Lembre-se da definição de árvore em grafos.
Alternativa por alternativa
O aluno acredita que basta ter poucas arestas para ser árvore, ignorando que o grafo pode estar desconectado e que a conectividade é exigida.
O aluno confunde a contagem de arestas com a estrutura: acredita que uma árvore pode ser desconectada, quando a conectividade é parte da definição.
Por que engana: Confundir a condição de conectividade com a quantidade de arestas, afirmando que um grafo desconectado pode ser uma árvore.
O aluno generaliza um caso trivial (grafo vazio) como se fosse a caracterização geral de árvores, sem considerar que a condição deve valer para qualquer V.
Teorema clássico: grafos conectados e acíclicos têm exatamente V-1 arestas; se um grafo conectado tem E=V-1 não há ciclos, portanto é árvore; a condição é necessária e suficiente.
O aluno acredita que mais arestas que vértices ainda formam árvore, sem perceber que um grafo conexo com V + 1 arestas necessariamente contém ciclo.
Raio-X da questão
condição de árvore em grafos
avaliacao
propriedades de grafos · conectividade em grafos
Revisar as propriedades de árvores em grafos.
Confundir a condição de conectividade com a quantidade de arestas, afirmando que um grafo desconectado pode ser uma árvore.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Dado um grafo não direcionado fornecido como matriz de adjacência, qual condição sobre os graus dos vértices e a…
- Em um grafo não direcionado, qual condição sobre o grau dos vértices garante a existência de um circuito Euleriano…
- Em um grafo conexo com pesos nas arestas, qual propriedade caracteriza uma árvore geradora mínima (MST)?
- Proponha um algoritmo para decidir se um grafo simples não direcionado possui circuito Euleriano. Indique que…
- Em um grafo simples não direcionado representado por lista de adjacência, o que caracteriza um vértice isolado e como…
- Um grafo não direcionado tem 4 vértices. Suas arestas são AB e BC. O grafo é conexo?
🔎 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