Descreva em passos um algoritmo que, recebendo a lista de adjacência de um grafo não direcionado, retorne…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Construir e simular algoritmos, de forma independente ou em colaboração, que resolvam problemas simples e do cotidiano com uso de sequências, seleções condicionais e repetições de instruções.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Descreva em passos um algoritmo que, recebendo a lista de adjacência de um grafo não direcionado, retorne todas as triplas de vértices que formam ciclos simples de tamanho 3 (triângulos) sem repetições.
✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.
Resposta esperada
Inicialize conjunto vazio T. 2) Para cada vértice u: para cada v em adj[u] com v>u: para cada w em adj[v] com w>v: se w está em adj[u] então adicionar tupla ordenada (u,v,w) a T. 3) Retornar T como lista. Garantir ordenação evita repetições; verifica arestas existentes em O(1) se adjacências são conjuntos.
Explicação
O algoritmo proposto explora cada vértice e suas adjacências de forma ordenada, garantindo que as triplas de vértices formem triângulos sem repetições. A condição de que v seja maior que u e w maior que v evita a contagem de combinações duplicadas. Além disso, a verificação da existência de arestas entre os vértices é feita de maneira eficiente, utilizando a estrutura de lista de adjacência.
Raio-X da questão
ciclos em grafos
avaliacao
ciclos em grafos · listas de adjacência
Revisar conceitos de grafos e algoritmos de busca.
O aluno pode confundir a definição de ciclo simples com outras estruturas de grafo, como caminhos ou ciclos de tamanho diferente.
ciencia_tecnologia
pensamento_critico
cientifico
Questões parecidas com resolução
- Lia criou um caminho no tabuleiro. O tablet usa “andar 10 passos”, e o robô usa “andar 1 quadrado”. Por que Lia escreveu…
- Algoritmo: "Ler nota. Se nota >= 60 então imprimir 'Aprovado'. Senão imprimir 'Reprovado'." Qual será a saída para nota…
- Na sala, um algoritmo manda ler a temperatura. Se ela for maior que 30 graus, deve ligar o ventilador; caso contrário…
- Descreva um algoritmo em pseudocódigo que, dado n variáveis booleanas (dados de entrada), gere todas as 2^n combinações…
- Projete um algoritmo em pseudocódigo que receba uma lista de nomes (strings) como dado de entrada e devolva uma lista de…
- Projete um algoritmo reativo (autômato) que filtra eventos duplicados recebidos de um sensor; cada evento tem campos…
🔎 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