Descreva sucintamente como verificar se um grafo simples não direcionado é k-regular usando sua lista de…

Questão

Descreva sucintamente como verificar se um grafo simples não direcionado é k-regular usando sua lista de adjacência; que operação deve ser aplicada a cada variável-lista?

1. A) Verificar se a soma dos comprimentos das listas adjacentes é igual a k.
2. B) Validar que cada lista de adjacência tem pelo menos k vértices.
3. C) Verificar que, para todo vértice v, o comprimento da lista adj[v] é igual a k; isto é, grau(v)=|adj[v]|=k para todos os v.
4. D) Verificar que todos os vértices têm o mesmo número de adjacentes, independentemente de que número é esse.
5. E) Contar o número total de arestas e dividir pelo número de vértices para obter k.

✅ Resposta correta: alternativa C

Resolução passo a passo

1. Em um grafo simples nao direcionado, cada vertice v possui uma lista de adjacencia adj[v] com seus vizinhos. Como nao ha laços nem arestas paralelas, o grau de v e exatamente o numero de elementos de adj[v], ou seja, grau(v) = |adj[v]|.
2. Ser k-regular significa que todo vertice tem grau k. Portanto, a operacao a aplicar a cada lista e calcular seu comprimento (cardinalidade) e compara-lo com k. Basta percorrer todos os vertices v e verificar se |adj[v]| = k; se algum falhar, o grafo nao e k-regular e a verificacao pode parar ali.
3. A alternativa A esta errada porque a soma dos comprimentos de todas as listas e igual a 2m (o dobro do numero de arestas), e nao o grau de cada vertice.
4. A alternativa B esta errada porque 'pelo menos k' descreve apenas um limite inferior para o grau (grau minimo), enquanto a regularidade exige igualdade exata com k.
5. A alternativa D esta errada porque ignora o valor k dado no enunciado: ter todos os graus iguais nao garante que o valor comum seja k.
6. A alternativa E esta errada porque m/n e apenas o grau medio. Um grau medio igual a k nao garante que cada vertice tenha grau k, pois alguns vertices podem ter grau maior e outros menor.
7. Conclusao: a alternativa C e a correta e coincide com o gabarito oficial.

💡 Dica: Considere a definição de k-regularidade 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 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…
• Projete um algoritmo (pseudocódigo) que, dado um grafo não direcionado representado por lista de adjacência dos bairros…
• Escreva em linguagem descritiva um algoritmo que, recebendo a lista de adjacência de um grafo não direcionado, retorne…
• Ao representar um grafo com listas de adjacência em um programa, que vantagem traz manter uma variável 'grau' para cada…
• Projete um algoritmo em alto nível que, dado um grafo simples não direcionado representado por lista de adjacência…

Todas as questões de Organização e representação da informação