Projete um algoritmo em alto nível que, dado um grafo simples não direcionado representado por lista de…
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
Projete um algoritmo em alto nível que, dado um grafo simples não direcionado representado por lista de adjacência, compute o número exato de arestas E sem duplicar contagens; explique também por que a soma dos graus é igual a 2E.
✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.
Resposta esperada
Algoritmo: d=0; para cada vértice v em V: d += len(adj[v]); E = d / 2. Alternativa (contagem direta): marcar pares visitados; para v em V: para u em adj[v]: se u>v então E+=1. Justificativa: em grafo não direcionado cada aresta {u,v} aparece nas duas listas adj[u] e adj[v], portanto soma dos graus = 2E.
Explicação
O algoritmo proposto conta o número total de conexões (graus) de todos os vértices e, como cada aresta é contada duas vezes (uma para cada extremidade), a divisão por 2 fornece o número exato de arestas. A justificativa esclarece que, em um grafo não direcionado, a aresta entre dois vértices é representada nas listas de adjacência de ambos, resultando na soma dos graus ser o dobro do número de arestas. Assim, a relação entre a soma dos graus e o número de arestas é uma consequência direta da estrutura do grafo.
Raio-X da questão
grafo simples, arestas, graus
avaliacao
grafo simples · lista de adjacência
Revisar a definição de grafo e a relação entre graus e arestas.
O aluno pode confundir a contagem de arestas, contando cada aresta duas vezes ao considerar os graus dos vértices.
ciencia_tecnologia
pensamento_critico
cientifico
Questões parecidas com resolução
- Em um grafo não direcionado representado por lista de adjacência, como se relaciona a soma dos graus de todos os…
- Escreva um algoritmo em linguagem descritiva que, recebendo uma lista de arestas (edge list) de um grafo com V vértices…
- Projete um algoritmo em alto nível (pseudocódigo) que converta um grafo simples não direcionado esparso dado por lista…
- Projete um algoritmo (pseudocódigo) que, dado um grafo não direcionado representado por lista de adjacência dos bairros…
- Escreva um algoritmo em linguagem descritiva que, dada a lista de adjacência de um grafo não direcionado e não…
- Escreva em linguagem descritiva um algoritmo que, recebendo a lista de adjacência de um grafo não direcionado, retorne…
🔎 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