Durante uma aula, os alunos precisam descobrir o menor caminho entre duas salas em uma escola, representadas…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Reconhecer objetos do mundo real e digital que podem ser representados através de grafos que estabelecem uma organização com uma quantidade variável de vértices conectados por arestas, fazendo manipulações simples sobre estas representações.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Durante uma aula, os alunos precisam descobrir o menor caminho entre duas salas em uma escola, representadas por um grafo. Se a sala A está conectada a B e C, e B está conectada a D, qual é o caminho mais curto de A até D?
- A) A -> C -> D
- B) A -> B -> D
- C) A -> B -> C
- D) A -> C -> B -> D
- E) A -> D
✅ Resposta correta: alternativa B
Resolução passo a passo
- Identifique as ligações do grafo a partir do enunciado: A está conectada a B e a C, e B está conectada a D. Não há informação de ligação direta entre A e D, nem entre C e D.
- Procure caminhos de A até D seguindo apenas essas ligações. O único caminho possível é A -> B -> D, que passa por 2 ligações (A-B e B-D).
- Verifique as alternativas erradas. A alternativa A (A -> C -> D) não é válida, pois C não está conectada a D. A alternativa C (A -> B -> C) leva a C, não a D. A alternativa D (A -> C -> B -> D) é um caminho válido, mas tem 3 ligações, então não é o menor. A alternativa E (A -> D) exigiria uma ligação direta entre A e D, que não existe no enunciado.
- Conclusão: o caminho mais curto de A até D é A -> B -> D, alternativa B, que coincide com o gabarito oficial.
💡 Dica: Desenhe o grafo para visualizar as conexões.
Alternativa por alternativa
Supõe que C também está ligada a D, como se houvesse uma ligação extra não informada no enunciado. Também pode ter tratado a ordem das letras como indicação de caminho.
Por que engana: Escolher um caminho que parece mais curto, mas que na verdade passa por mais arestas do que o necessário.
Esse é o caminho mais curto, utilizando 2 arestas.
Procura um caminho que passa por B mas esquece que o destino é D, parando em C. Lê o caminho como uma sequência de vértices visitados sem verificar se chega ao destino pedido.
Acredita que qualquer caminho que chegue a D serve como resposta, sem comparar o tamanho dos caminhos. Confunde caminho com menor caminho e não percebe que A -> B -> D é mais curto.
Confunde caminho mais curto com ligação direta visível, achando que A e D devem estar ligadas porque são os extremos da pergunta. Não percebe que o caminho mais curto pode passar por vértices intermediários.
Raio-X da questão
caminho em grafo
avaliacao
representacao de grafos · caminhos em grafos
Revisar conceitos de grafos e caminhos mais curtos.
Escolher um caminho que parece mais curto, mas que na verdade passa por mais arestas do que o necessário.
ciencia_tecnologia
tomada_decisao
cotidiano
Questões parecidas com resolução
- Na escola, Lia desenhou um grafo com pontos para representar a sala, a biblioteca e a quadra. As linhas mostram os…
- Ao projetar um algoritmo para calcular o caminho mais curto entre salas em um mapa da escola, qual representação de…
- Na escola, cada caminho até a biblioteca tem uma distância em quilômetros. Qual algoritmo encontra o caminho mais curto?
- Texto curto: grafo com vértices {A,B,C,D} e arestas AB, BC, CD. Aplicando definição de caminho, qual sequência é um…
- Descreva como você organizaria um algoritmo para encontrar o caminho mais curto em um grafo que liga três cidades: A, B…
- 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…
🔎 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