Imagine um grafo que modela amizades em uma vila: o vértice P liga-se a A, B e C; A e B não se conectam entre…
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
Imagine um grafo que modela amizades em uma vila: o vértice P liga-se a A, B e C; A e B não se conectam entre si; C conecta ao resto da vila. Usando termos como 'articulação' e 'algoritmo', avalie se remover P desconecta o grafo e proponha passos algorítmicos para identificar vértices de articulação.
✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.
Resposta esperada
Remover P desconecta a vila se A e B ficarem isolados de C e do restante; P é vértice de articulação. Modelo de detecção: executar DFS marcando tempo de descoberta (disc) e menor alcance (low) para cada vértice; P é articulação se existir filho v de P tal que low[v] = disc[P], ou se P for raiz com dois ou mais filhos. Passos: 1) inicializar disc e low; 2) rodar DFS recursiva atribuindo disc/time; 3) atualizar low dos ancestrais via back-edges; 4) aplicar condições acima para reportar articulações; complexidade O(V+E).
Explicação
A explicação aborda a definição de vértice de articulação, que é crucial para entender como a remoção de P afeta a conectividade do grafo. O uso do algoritmo DFS para calcular os tempos de descoberta e menor alcance permite identificar eficientemente os vértices de articulação. Além disso, a descrição dos passos do algoritmo e sua complexidade fornecem uma abordagem clara e prática para resolver o problema apresentado.
Raio-X da questão
vértices de articulação
avaliacao
teoria dos grafos · algoritmos de busca
Revisar conceitos de grafos e algoritmos de busca.
O aluno pode confundir a definição de vértice de articulação com outros conceitos de grafos, como arestas ou ciclos, levando a uma avaliação incorreta da desconexão do grafo.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Projete um algoritmo (pseudocódigo) que, dado um grafo não direcionado representado por lista de adjacência, determine…
- 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…
- João tem um conjunto de amigos e quer saber quem pode se conectar a quem. Se ele desenhar um grafo com seus amigos como…
- Descreva como representar a rede de amizades de uma turma como um grafo e detalhe um procedimento passo a passo para…
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