Que critério algorítmico identifica uma aresta como 'ponte' em um grafo conectado e qual técnica eficiente…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Identificar as principais formas de organizar e representar a informação de maneira estruturada (matrizes, registros, listas e grafos) ou não estruturada (números, palavras, valores verdade).
Fonte: Base Nacional Comum Curricular (MEC).Questão
Que critério algorítmico identifica uma aresta como 'ponte' em um grafo conectado e qual técnica eficiente permite detectá-las?
- A) A técnica para identificar arestas ponte é feita por análise de matriz de adjacência.
- B) Uma aresta é ponte se sua remoção aumenta o número de componentes; detecta-se via DFS usando tempos de descoberta e valores low (algoritmo em O(V+E)).
- C) Detectar arestas ponte não requer análise por DFS.
- D) Uma aresta é ponte se sua remoção diminui a quantidade de vértices no grafo.
- E) Remover uma aresta sempre aumenta o número de componentes do grafo.
✅ Resposta correta: alternativa B
Resolução passo a passo
- Uma aresta ponte (bridge) é uma aresta cuja remoção desconecta o grafo, ou seja, aumenta o número de componentes conexas. Equivalentemente, ela não pertence a nenhum ciclo.
- A técnica eficiente clássica é a DFS (busca em profundidade) com o cálculo dos tempos de descoberta (disc) de cada vértice e do valor low, que é o menor tempo de descoberta alcançável a partir da subárvore do vértice usando no máximo uma aresta de retorno. Uma aresta árvore (u, v), com v filho de u, é ponte quando low[v] > disc[u].
- Como cada vértice e cada aresta são visitados uma única vez, o algoritmo (de Tarjan) roda em O(V+E).
- Verificando as alternativas, a B reúne o critério correto (aumento de componentes) e a técnica correta (DFS com disc e low, O(V+E)).
- A alternativa A está errada, pois matriz de adjacência não é a forma usual de identificar pontes, e a análise direta por ela custaria mais que O(V+E). A alternativa C está errada, pois a DFS é justamente a técnica padrão para isso. A alternativa D está errada, pois remover uma aresta não altera o número de vértices. A alternativa E está errada, pois remover uma aresta só aumenta o número de componentes se ela for ponte; em arestas de ciclo, o número de componentes permanece igual.
- Conclusão: o gabarito B está correto.
💡 Dica: Considere as definições de ponte e as técnicas de busca em grafos.
Alternativa por alternativa
O aluno acredita que a estrutura de dados usada para representar o grafo determina diretamente a identificação das pontes, confundindo a representação com o algoritmo.
Por que engana: Confundir a definição de aresta ponte, acreditando que sua remoção sempre diminui o número de vértices, sem considerar a estrutura do grafo.
Durante DFS calcula-se discovery[u] e low[v]; para aresta (u,v), se low[v]>discovery[u] então não há caminho alternativo e a aresta é ponte; o processo visita cada aresta/vertice uma vez, total O(V+E).
O aluno supõe que, por se tratar de propriedade estrutural, não é necessário um procedimento de busca no grafo, quando na verdade a DFS é a técnica padrão.
O aluno confunde remoção de aresta com remoção de vértice, imaginando que retirar uma aresta reduz o número de vértices do grafo.
O aluno generaliza que toda remoção de aresta aumenta as componentes, ignorando que arestas que pertencem a ciclos mantêm o grafo conectado.
Raio-X da questão
arestas em grafos
avaliacao
grafos e suas propriedades · busca em profundidade (DFS)
Revisar conceitos de grafos e algoritmos de busca.
Confundir a definição de aresta ponte, acreditando que sua remoção sempre diminui o número de vértices, sem considerar a estrutura do grafo.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Projete um algoritmo (explique a ideia e apresente pseudocódigo) que, dado um grafo não direcionado em lista de…
- Qual técnica algorítmica permite detectar ciclos em um grafo dirigido em tempo O(V+E)?
- Descreva um algoritmo em alto nível que, dado um grafo não direcionado representado por lista de adjacência, identifique…
- Descreva um algoritmo em alto nível que, dado um grafo não direcionado representado por lista de adjacência, identifique…
- Descreva um algoritmo baseado em DFS para identificar vértices de articulação (cut vertices) em um grafo não direcionado…
- Para encontrar o menor número de arestas entre dois vértices em um grafo não ponderado, qual algoritmo é mais adequado e…
🔎 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