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
- A professora fez uma tabela: os grupos ficam nas linhas, os dias da semana ficam nas colunas e cada espaço mostra a…
- Um aplicativo percebe quais fotos mostram animais. O que ele pode fazer para achar essas fotos mais rápido? O que o…
- Em Manaus, a escola testa um programa que separa mensagens em urgente e comum. Aplique a ideia de classificacao e…
- Desenhe um grafo que represente uma rota de entregas entre três escolas (E1, E2, E3) e dois pontos de apoio (P1, P2)…
- Um mapa de estações de metrô em que as estações estão ligadas por linhas pode ser representado como um grafo? Escreva a…
- Escolha um exemplo do cotidiano (por exemplo: contatos em um aplicativo da escola ou paradas de ônibus) e descreva como…
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