Em um grafo não direcionado representado por lista de adjacência, que variável e que operação um algoritmo…

Questão

Em um grafo não direcionado representado por lista de adjacência, que variável e que operação um algoritmo deve usar para calcular o grau de um vértice v?

1. A) Usar uma variável booleana 'temVizinho' e definir true para cada vizinho; true indica grau.
2. B) Iniciar o contador em 1 e incrementar por cada entrada na lista de adjacência.
3. C) Somar os graus de todos os vértices vizinhos para obter o grau de v.
4. D) Usar uma variável inteira contador iniciada em 0; iterar pela lista de adjacência de v e incrementar o contador para cada entrada (vizinho).
5. E) Contar o número total de arestas do grafo e dividir por dois para achar o grau de v.

✅ Resposta correta: alternativa D

Resolução passo a passo

1. O grau de um vértice v em um grafo não direcionado é o número de arestas incidentes a v. Em uma lista de adjacência, cada vizinho de v aparece uma única vez na lista de v, então o grau é exatamente o número de entradas dessa lista. Passo 2: Para contar, o algoritmo precisa de uma variável inteira contador, iniciada em 0, que representa quantas arestas já foram contadas. Passo 3: Em seguida, percorre-se a lista de adjacência de v e, para cada entrada (cada vizinho), incrementa-se o contador em 1. Ao final, o contador guarda o grau de v. Passo 4: Por que as outras estão erradas: A usa booleana, que só indica existência de vizinho e perde a quantidade de vizinhos. B começa em 1, o que soma um a mais do que o correto. C confunde grau de v com a soma dos graus dos vizinhos, que é outra grandeza. E calcula o total de arestas do grafo, que não é o grau de um vértice específico. Passo 5: Conclusão: a alternativa correta é a D, que coincide com o gabarito oficial.

💡 Dica: Considere a lista de adjacência e conte as conexões do vértice.

Alternativa por alternativa

Raio-X da questão

Questões parecidas com resoluçã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…
• Ao representar um grafo com listas de adjacência em um programa, que vantagem traz manter uma variável 'grau' para cada…
• 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 não dirigido, o termo 'grau' de um vértice refere-se a qual quantidade?
• Escreva um algoritmo em linguagem descritiva que, recebendo a matriz de adjacência de um grafo não direcionado com V…
• Numa rede de sensores, um algoritmo registra o número de conexões de cada nó (grau). Qual alternativa identifica…

Todas as questões de Programação - Propriedades de grafos