A tabela de arestas (dados) de um grafo dirigido é: 1?2, 2?3, 3?1, 3?4. Usando um algoritmo de detecção…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Criar soluções de problemas para os quais seja adequado o uso de árvores e grafos para descrever suas informações e automatizá-las usando uma linguagem de programação.
Fonte: Base Nacional Comum Curricular (MEC).Questão
A tabela de arestas (dados) de um grafo dirigido é: 1?2, 2?3, 3?1, 3?4. Usando um algoritmo de detecção, analise se existe ciclo e qual alternativa explica corretamente o motivo.
- A) Não existe ciclo; caminho termina em 4 sem retorno.
- B) Detecção de ciclo exige algoritmo de caminhos mínimos e comparação de distâncias.
- C) Existe ciclo 1?2?3?1; detectável por DFS que encontra vértice já na pilha de recursão.
- D) Há ciclo apenas se o grafo for considerado não direcionado.
- E) Só há ciclo se existir aresta 4?1 para fechar um laço envolvendo 4.
✅ Resposta correta: alternativa C
Resolução passo a passo
- Interpretar os dados. O símbolo ? representa a seta de direção de cada aresta, logo as arestas são 1→2, 2→3, 3→1 e 3→4. Passo 2: Verificar se existe ciclo seguindo as setas a partir do vértice 1: 1→2, depois 2→3, depois 3→1, voltando ao ponto de partida. Esse laço 1→2→3→1 é um ciclo. Passo 3: Ver como um algoritmo detecta isso. Na DFS (busca em profundidade), ao visitar o vértice 3 e tentar a aresta 3→1, o vértice 1 ainda está na pilha de recursão (ainda não terminou de ser explorado). Uma aresta que aponta para um vértice da pilha de recursão é uma aresta de retorno, e isso caracteriza ciclo. Passo 4: Por que a alternativa A está errada: o caminho 1→2→3→4 de fato termina em 4, mas existe outro caminho, 1→2→3→1, que retorna ao início, então a conclusão de que não há ciclo está incompleta. Passo 5: Por que a alternativa B está errada: detectar ciclo não exige caminhos mínimos nem comparação de distâncias; a DFS basta. Passo 6: Por que a alternativa D está errada: a questão trata de grafo dirigido, e o ciclo existe justamente por causa das direções das arestas; considerar o grafo não direcionado mudaria o problema. Passo 7: Por que a alternativa E está errada: o ciclo 1→2→3→1 não passa pelo vértice 4, então não é preciso nenhuma aresta 4→1 para que ele exista. Conclusão: a alternativa correta é a C, que identifica corretamente o ciclo 1→2→3→1 e o método de detecção por DFS, em concordância com o gabarito oficial.
💡 Dica: Analise as arestas e verifique a presença de ciclos.
Alternativa por alternativa
O aluno segue apenas o caminho 1→2→3→4, que não retorna, e conclui que não há ciclo, sem testar a aresta 3→1 que fecha o laço.
Por que engana: Confundir a definição de ciclo em um grafo dirigido, acreditando que a ausência de arestas de retorno implica na inexistência de ciclos.
O aluno acredita que detectar ciclo exige algoritmos de caminhos mínimos como Dijkstra e comparação de distâncias, confundindo dois problemas diferentes de grafos.
Correto: DFS identifica um vértice visitado que ainda está na pilha, apontando ciclo dirigido.
O aluno acha que a noção de ciclo depende de o grafo ser não direcionado, ignorando que a questão trata de arestas com sentido e que o laço 1→2→3→1 já existe no grafo dirigido.
O aluno supõe que o ciclo precisa envolver o vértice 4 ou depender de uma aresta de retorno a partir dele, e não percebe que o laço 1→2→3→1 não passa por 4.
Raio-X da questão
ciclo em grafo dirigido
avaliacao
grafo dirigido · algoritmos de busca
Revisar algoritmos de detecção de ciclos em grafos.
Confundir a definição de ciclo em um grafo dirigido, acreditando que a ausência de arestas de retorno implica na inexistência de ciclos.
ciencia_tecnologia
pensamento_critico
cientifico
Questões parecidas com resolução
- Qual técnica algorítmica permite detectar ciclos em um grafo dirigido em tempo O(V+E)?
- Projete um algoritmo em pseudocódigo para detectar ciclos em um grafo dirigido representado por listas de adjacência…
- Matriz de adjacência 4×4 com vértices A,B,C,D: [[0,1,0,1],[1,0,1,0],[0,1,0,1],[1,0,1,0]]. Avalie se ela representa um…
- Descreva, em pseudocódigo, um algoritmo que receba como dado um grafo direcionado G = (V,E) representando dependências…
- 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…
- Um programa recebe um grafo dirigido que representa pré-requisitos entre disciplinas (nó = disciplina; aresta A?B indica…
Todas as questões de Programação - Programação usando grafos e árvores
🔎 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