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
- Na mesa há duas garrafas azuis de 500 mL e dois moletons cinza. As garrafas têm adesivos diferentes, e os moletons têm…
- Considere um grafo que representa salas A, B, C e D com arestas A–B, B–C, C–D e B–D. Qual aresta deve ser removida para…
- Em uma praça há cinco bancos identificados B1, B2, B3, B4 e B5 ligados por caminhos entre: B1–B2, B2–B3, B3–B4 e B4–B5…
- Descreva como representar a rede de amizades de uma turma como um grafo e detalhe um procedimento passo a passo para…
- Em um grafo ponderado que modela ruas de uma cidade, como representar na aresta tanto a distância quanto o tempo de…
- Em um algoritmo de busca em profundidade (DFS) em um grafo que precisa rastrear o caminho atual para detecção de ciclos…
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