Em um software de organização de tarefas, as atividades podem ser representadas como nós em um grafo. Se há…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Utilizar algoritmos clássicos de manipulação sobre listas.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Em um software de organização de tarefas, as atividades podem ser representadas como nós em um grafo. Se há conexões de mão única de A para B e de A para C, e de B para D, quantos caminhos sem repetir nós existem para ir de A a D?
- A) Nenhum caminho.
- B) Dois caminhos.
- C) Um caminho.
- D) Três caminhos.
- E) Quatro caminhos.
✅ Resposta correta: alternativa C
Resolução passo a passo
- Represente o grafo com as conexões dirigidas dadas: A para B, A para C e B para D. Como as conexões são de mão única, só é possível andar no sentido das setas.Passo 2: Liste os caminhos que saem de A. Ir para C leva a um beco sem saída, pois não há nenhuma seta saindo de C. Ir para B permite seguir para D.Passo 3: O único caminho de A até D sem repetir nós é A -> B -> D. Ele passa por nós distintos e respeita o sentido de cada seta.Passo 4: Por isso a resposta é um caminho, alternativa C, que coincide com o gabarito oficial. Alternativa A está errada, pois existe pelo menos um caminho. Alternativa B está errada, pois o ramo A -> C não chega a D. Alternativa D está errada, pois conta arestas e não caminhos completos. Alternativa E está errada, pois conta trechos parciais como caminhos.
💡 Dica: Siga as conexões direcionadas a partir de A e verifique quais alcançam D sem repetir nós.
Alternativa por alternativa
Acredita que, como não há uma conexão direta de A até D, não existe nenhum caminho. Não percebe que o caminho pode ter etapas intermediárias.
Conta os dois ramos que saem de A (A para B e A para C) como dois caminhos completos até D. Não percebe que o ramo A para C é um beco sem saída.
Por que engana: Contar A→C como um caminho até D, embora não haja conexão de C a D, ou desconsiderar a direção das arestas.
Para chegar de A a D, é preciso passar por B, pois há uma conexão de B para D. Assim, o caminho é A–B–D.
Conta as três conexões do grafo como se cada uma fosse um caminho até D. Confunde número de arestas com número de caminhos completos.
Soma todos os trechos possíveis (A para B, A para C, B para D e A até D passando por B), tratando trechos parciais como caminhos até D. Não considera que o caminho precisa terminar em D.
Raio-X da questão
Caminhos em grafos direcionados
avaliacao
Nós e arestas em grafos · Direção das conexões
Revise grafos direcionados, nós, arestas e a identificação de caminhos sem repetição de nós.
Contar A→C como um caminho até D, embora não haja conexão de C a D, ou desconsiderar a direção das arestas.
ciencia_tecnologia
tomada_decisao
cientifico
Questões parecidas com resolução
- Um sistema de uma estufa analisa cinco leituras de umidade do solo: 19, 22, 24, 27 e 20. O algoritmo conta as leituras…
- Na montagem de um boletim digital da escola, as seções estão nesta ordem: capa, entrevista, fotos e agenda. A equipe…
- Em um aplicativo da escola, a lista de representantes da turma aparece nesta ordem: Ana, Bia, Caio, Davi e Elisa. Caio…
- Enquanto agentes de manutenção acompanham pedidos de reparo de bicicletas públicas, o painel registra os chamados em uma…
- — O livro de Marina Souza está disponível? — perguntou uma visitante ao balcão da biblioteca municipal. No computador…
- — O kit 47 já foi devolvido? — perguntou a técnica responsável pela campanha itinerante de vacinação. Antes do uso de…
🔎 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