Uma equipe de estudantes está modelando, como um grafo dirigido, as conexões entre estações de bicicletas de…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Explorar e construir a solução de problemas por meio de refinamentos, utilizando diversos níveis de abstração desde a especificação até a implementação.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Uma equipe de estudantes está modelando, como um grafo dirigido, as conexões entre estações de bicicletas de uma cidade. Cada vértice representa uma estação, e cada seta representa um trajeto permitido em um único sentido. O grafo possui as seguintes conexões: A?B, A?C, B?D, C?D, D?F e E?F. Para verificar se uma bicicleta pode sair da estação A e chegar à estação F, é preciso analisar as conexões seguindo os vértices alcançados. Com base no texto, qual procedimento permite determinar corretamente se existe um caminho da estação A até a estação F?
- A) Examinar somente as conexões diretas de A para F.
- B) Contar todas as arestas e comparar esse total com F.
- C) Verificar apenas se F possui alguma conexão de saída.
- D) Comparar os nomes das estações e verificar se coincidem.
- E) Executar uma busca em profundidade e verificar se F é alcançada.
✅ Resposta correta: alternativa E
Resolução passo a passo
- No enunciado, as setas aparecem com o caractere "?" (provável falha de codificação). Interpreto cada conexão como um trajeto em um sentido: A→B, A→C, B→D, C→D, D→F e E→F. Passo 2: Para saber se há caminho de A até F, é preciso seguir as setas a partir de A e verificar se F é alcançada, passando por vértices intermediários. Passo 3: Isso é exatamente o que a busca em profundidade faz: parte de A, visita B (A→B), depois D (B→D) e então F (D→F). Como F foi alcançada, existe caminho A→B→D→F. Passo 4: Por que as outras alternativas estão erradas: A) olhar só as ligações diretas falha, pois A não se liga diretamente a F e o caminho tem três trechos. B) contar arestas não diz nada sobre alcançabilidade entre dois vértices específicos. C) verificar saídas de F é inútil, pois o trajeto parte de A e a pergunta é se chega a F, então o que importa são as setas que entram em F. D) comparar nomes de estações não revela conexões no grafo. Passo 5: Conclusão: o procedimento correto é percorrer o grafo a partir de A seguindo as setas (busca em profundidade ou em largura) e verificar se F é atingida.
💡 Dica: Acompanhe os vértices alcançados a partir de A usando uma busca em profundidade até verificar se F foi alcançada.
Alternativa por alternativa
O aluno acredita que só existe caminho se houver uma seta direta de A para F. Ele ignora que um trajeto pode passar por vértices intermediários.
Por que engana: O aluno pode considerar apenas conexões diretas ou confundir a existência de uma conexão de saída de F com a possibilidade de alcançar F a partir de A.
O aluno confunde conectividade com contagem de arestas, achando que o número total de conexões responde se duas estações estão ligadas por um percurso.
O aluno inverte a direção da análise, olhando para as saídas de F quando deveria verificar se algum trajeto que parte de A chega até F.
O aluno pensa que a ligação entre estações depende de seus nomes, como se a identificação textual dos vértices indicasse conexão. Ele não relaciona a estrutura do grafo com a pergunta.
A busca em profundidade percorre, a partir de A, os vértices acessíveis pelas conexões. Nesse grafo, ela pode seguir A→B→D→F ou A→C→D→F e, ao alcançar F, confirma a existência de um caminho. O procedimento também permitiria concluir que não há caminho caso todos os vértices alcançáveis fossem examinados sem encontrar F.
Raio-X da questão
busca em profundidade em grafos
avaliacao
conceito de grafo dirigido · vértices e arestas
Revise grafos dirigidos, vértices, arestas e algoritmos de busca em profundidade.
O aluno pode considerar apenas conexões diretas ou confundir a existência de uma conexão de saída de F com a possibilidade de alcançar F a partir de A.
ciencia_tecnologia
tomada_decisao
cientifico
Questões parecidas com resolução
- No aplicativo de trilhas de um parque de preservacao, cada abrigo de descanso aparece como um ponto, e cada caminho…
- "Se um corredor ficar bloqueado, a gente precisa ter uma volta sem se perder", explicou a monitora de um parque ao…
- Durante uma aula, os alunos precisam descobrir o menor caminho entre duas salas em uma escola, representadas por um…
- Um mapa mostra cinco cidades e as estradas diretas entre elas. As estradas existentes são: A–B, A–C, B–D e C–E. Não há…
- Uma prefeitura está desenvolvendo um aplicativo para orientar ciclistas entre cinco cruzamentos de uma cidade. Para…
- No painel de um aplicativo de mobilidade, a equipe de desenvolvimento registrou os pontos de aluguel de bicicletas da…
🔎 Resolver outra questão
Cole o enunciado e veja a resolução passo a passo, a alternativa correta e por que as outras estão erradas.
Professor: monte a prova com questões como esta, com gabarito e folha de respostas, em 30 segundos. Ver planos · Blog