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
- Em uma corrida de obstáculos, os corredores precisam seguir um caminho específico em um gráfico. Se o corredor A vai do…
- Em um grafo não direcionado e simples, os vértices A, B, C e D têm graus 1, 2, 2 e 3, respectivamente. Qual é o número…
- Texto curto: grafo com vértices {A,B,C,D} e arestas AB, BC, CD. Aplicando definição de caminho, qual sequência é um…
- "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…
- Considere a lista de objetos: A, B, C, D. Se A está conectado a B, B a C e C a D, como isso é representado em um grafo?
🔎 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