Em um grafo simples não direcionado, defina o termo "grau" de um vértice e explique como obtê-lo a partir da…

Questão

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 adjacência.

1. A) O grau é o número de arestas incidentes; obtém-se contando as entradas na lista de adjacência do vértice.
2. B) O grau de um vértice é o total de vértices no grafo.
3. C) O grau pode ser obtido somando todos os valores de peso das arestas do grafo.
4. D) O grau é a média dos graus dos vizinhos do vértice.
5. E) O grau de um vértice é a soma dos pesos das arestas incidentes.

✅ Resposta correta: alternativa A

Resolução passo a passo

1. Em um grafo simples não direcionado, o grau de um vértice v é o número de arestas incidentes a ele, ou seja, quantas arestas têm v como uma de suas extremidades.
2. Na representação por lista de adjacência, cada vértice possui uma lista com os seus vizinhos. Cada aresta {u, v} aparece na lista de u (com v) e na lista de v (com u). Por isso, o grau de v é simplesmente o número de entradas na lista de adjacência de v.
3. Assim, a alternativa A está correta: define grau corretamente como número de arestas incidentes e indica o procedimento de contar as entradas da lista do vértice.
4. A alternativa B está errada, pois confunde grau com a quantidade de vértices do grafo, que é a ordem do grafo.
5. A alternativa C está errada, pois grafos não ponderados não possuem pesos e, mesmo em grafos ponderados, o grau não é a soma dos pesos de todo o grafo; somar todos os graus dá o dobro do número de arestas.
6. A alternativa D está errada, pois a média dos graus dos vizinhos é uma grandeza diferente (usada em outras métricas), não a definição de grau.
7. A alternativa E está errada, pois ela mistura o conceito de grau com o de peso ponderado; no grafo simples não direcionado o grau conta arestas, não soma pesos.
8. Conclusão: o gabarito oficial A está correto.

💡 Dica: Defina o grau e analise a lista de adjacência.

Alternativa por alternativa

Raio-X da questão

Questões parecidas com resolução

• Em um grafo não dirigido, o termo 'grau' de um vértice refere-se a qual quantidade?
• 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 não direcionado representado por lista de adjacência, como se relaciona a soma dos graus de todos os…
• Em um grafo simples não direcionado representado por lista de adjacência, o que caracteriza um vértice isolado e como…
• Defina, em termos de grafo, o que é uma lista de adjacência e que informação ela armazena para cada vértice (use os…
• Ao representar um grafo com listas de adjacência em um programa, que vantagem traz manter uma variável 'grau' para cada…

Todas as questões de Programação - Tipos de dados