Num grafo que é uma árvore com 7 vértices, quantas arestas o algoritmo precisa considerar para percorrer todos…
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
Num grafo que é uma árvore com 7 vértices, quantas arestas o algoritmo precisa considerar para percorrer todos os nós sem formar ciclos?
- A) Uma árvore com 7 vértices sempre se divide em dois gráficos separados.
- B) Uma árvore com n vértices tem n + 1 arestas necessárias.
- C) Num grafo em forma de árvore com 7 vértices, precisam ser consideradas 7 arestas.
- D) 6 arestas (uma árvore com n vértices tem n - 1 arestas).
- E) São necessárias 5 arestas para uma árvore com 7 nós.
✅ Resposta correta: alternativa D
Resolução passo a passo
- Uma árvore é um grafo conexo e sem ciclos. Ela é a forma mínima de manter todos os vértices ligados sem criar caminhos fechados.
- Para percorrer todos os nós sem formar ciclos, o grafo precisa de exatamente n - 1 arestas, em que n é o número de vértices. Com n = 7, temos 7 - 1 = 6 arestas.
- Uma forma de conferir é construir a árvore aos poucos. Começando com 1 vértice isolado, cada vértice novo ligado à estrutura exige exatamente uma aresta, e são 6 inclusões para chegar a 7 vértices.
- A alternativa A está errada porque uma árvore é conexa e não se divide em dois gráficos separados; se fosse desconexa, deixaria de ser árvore.
- A alternativa B está errada porque n + 1 arestas daria 8 arestas, o que já fecha pelo menos um ciclo em uma árvore com 7 vértices.
- A alternativa C está errada porque confunde a quantidade de vértices com a de arestas; 7 arestas também geraria pelo menos um ciclo.
- A alternativa E está errada porque 5 arestas (n - 2) deixariam o grafo desconexo, com pelo menos duas componentes, o que impede percorrer todos os nós.
- Resposta: alternativa D, que coincide com o gabarito oficial.
💡 Dica: Lembre-se que em uma árvore, o número de arestas é sempre um a menos que o número de vértices.
Alternativa por alternativa
O aluno acredita que a árvore, por ser um grafo com poucas arestas, se separa em partes isoladas. Confunde a propriedade de conexidade com a ideia de ter poucas conexões.
O aluno supõe que é preciso uma aresta a mais que o número de vértices para garantir a ligação, possivelmente generalizando de grafos com ciclo ou aplicando uma fórmula decorada de forma errada.
O aluno iguala o número de arestas ao número de vértices, por intuição de que cada vértice precisa de uma ligação própria. Não percebe que a aresta conecta dois vértices.
Por que engana: Confundir o número de arestas em uma árvore, acreditando que é igual ao número de vértices.
Por definição, uma árvore conexa sem ciclos com n vértices tem exatamente n-1 arestas; para 7 vértices são 6 arestas.
O aluno subtrai 2 do número de vértices, talvez lembrando de alguma fórmula parecida ou fazendo a conta mal. Não percebe que, com 5 arestas, sobra pelo menos um vértice desconectado.
Raio-X da questão
árvore em grafos
avaliacao
propriedades de árvores em grafos · número de arestas em grafos
Revisar as propriedades das árvores em grafos.
Confundir o número de arestas em uma árvore, acreditando que é igual ao número de vértices.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Se um grafo contém 8 vértices e é um ciclo, quantas arestas ele possui?
- Em um grafo com 5 vértices, quantas arestas são necessárias para conectar todos os vértices de forma que todos estejam…
- Considere uma árvore com 5 nós. Qual a quantidade máxima de arestas que ela pode ter?
- Uma equipe de estudantes está analisando uma rede simples de quatro estações de monitoramento. Cada estação pode estar…
- Um grafo completo não direcionado tem 6 vértices. Qual é o número de arestas?
- Se um grafo é representado por lista de adjacência com V vértices e E arestas, qual a complexidade em notação O de um…
Todas as questões de Organização e representação da informação
🔎 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