Em um grafo não direcionado representado por lista de adjacência, como se relaciona a soma dos graus de todos…
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
Em um grafo não direcionado representado por lista de adjacência, como se relaciona a soma dos graus de todos os vértices com o número total de arestas m? Use os termos grau e aresta.
- A) A soma dos graus de todos os vértices é igual a m/2.
- B) A soma dos graus de todos os vértices é igual a 2^m.
- C) A soma dos graus de todos os vértices é igual a 2m + n (n vértices).
- D) A soma dos graus de todos os vértices é igual a 2m (duas vezes o número de arestas).
- E) A soma dos graus de todos os vértices é igual a m.
✅ Resposta correta: alternativa D
Resolução passo a passo
- Em um grafo não direcionado, cada aresta liga dois vértices distintos (u e v). Ao contar graus, a aresta é contada uma vez em grau(u) e outra vez em grau(v), ou seja, ela contribui com 2 para a soma dos graus. Passo 2: Como há m arestas, cada uma contribuindo com 2, a soma dos graus de todos os vértices é 2m. Essa é a relação chamada de lema do aperto de mãos. Passo 3: Exemplo: um triângulo tem 3 vértices, cada um de grau 2, então a soma dos graus é 2+2+2 = 6. Como o triângulo tem m = 3 arestas, 2m = 6, o que confirma a relação. Passo 4: A alternativa A está errada, pois m/2 divide em vez de multiplicar. A alternativa B está errada, pois 2^m é uma potência que não tem relação com a contagem de graus. A alternativa C está errada, pois a soma dos graus não depende do número de vértices n somado a 2m. A alternativa E está errada, pois m conta cada aresta uma única vez e ignora que ela tem duas extremidades. Gabarito oficial D confirmado.
💡 Dica: Considere a relação entre graus e arestas em grafos.
Alternativa por alternativa
O aluno provavelmente acha que cada aresta fornece metade de uma contribuição para a soma, invertendo a operação de multiplicação por 2 para divisão por 2.
Por que engana: Confundir a relação entre a soma dos graus dos vértices e o número de arestas, podendo pensar que é igual a m ou m/2.
O aluno confunde a relação linear entre graus e arestas com crescimento exponencial, possivelmente lembrando de fórmulas como o número de subconjuntos de arestas.
O aluno acredita que o número de vértices n entra somado na fórmula, misturando a soma dos graus com uma contagem de vértices que não se relaciona diretamente com ela.
Cada aresta conecta dois vértices e contribui com 1 ao grau de cada extremidade; assim cada aresta é contada duas vezes na soma dos graus.
O aluno entende que cada aresta contribui apenas 1 para a soma dos graus, esquecendo que a aresta tem duas extremidades e é contada em dois vértices.
Raio-X da questão
grafo não direcionado
avaliacao
grafo não direcionado · lista de adjacência
Revisar a definição de grau de vértice e arestas em grafos.
Confundir a relação entre a soma dos graus dos vértices e o número de arestas, podendo pensar que é igual a m ou m/2.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Projete um algoritmo em alto nível que, dado um grafo simples não direcionado representado por lista de adjacência…
- Em um grafo não direcionado representado por lista de adjacência, que variável e que operação um algoritmo deve usar…
- Em um grafo simples não direcionado, defina o termo "grau" de um vértice e explique como obtê-lo a partir da lista de…
- Em um grafo não dirigido, o termo 'grau' de um vértice refere-se a qual quantidade?
- Qual a relação entre vértices e arestas em um grafo?
- Em um grafo não direcionado, como se representa a relação entre dois vértices?
Todas as questões de Organização e representação da informação
🔎 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