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 denso, qual representação — matriz de adjacência ou lista de adjacência — permite verificar em tempo…
• Em um grafo simples não direcionado representado por lista de adjacência, o que caracteriza um vértice isolado e como…
• Descreva com precisão o algoritmo e as estruturas de dados (registros, hash ou listas) para construir um índice…
• Em um autômato orientado por eventos que registra leituras periódicas de um sensor, qual estrutura de dados é mais…
• Projete um autômato baseado em eventos para gerenciar reservas de salas multimídia na escola: descreva estados, eventos…
• Considerando um grafo com n vértices e m arestas que representa conexões entre pontos de coleta de dado, qual…

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