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
- Em um projeto de monitoramento de rios, uma boia computacional organiza leituras de sensores antes de enviá-las por…
- Uma biblioteca escolar recebeu caixas de livros doados para uma feira de troca. Para registrar os exemplares, a equipe…
- Um centro cultural público oferece inscrições on-line para atividades com critérios variados. Na oficina de teatro…
- Uma escola está testando dois protótipos de aplicativo para que estudantes consultem mudanças de sala, horários e…
- Uma secretaria municipal de educação está digitalizando pedidos de transporte escolar e de atendimento em contraturno…
- — O cartaz não pode sair duas vezes, pois a feira começa em uma hora — alertou a coordenadora do centro cultural. No…
🔎 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