Pergunta 3
1 pts
Considere as sentenças abaixo sobre um grafo G=(V,A):
i. Uma matriz de adjacência é a estrutura de dados ideal para armazenar grafos
esparsos.
ii. A lista de adjacência é a estrutura de dados ideal para armazenar grafos densos.
iii. Uma árvore é um grafo acíclico e conexo.
Soluções para a tarefa
Resposta:
Apenas a iii está correta!
Explicação passo-a-passo:
As Listas de Adjacência são geralmente preferidas por sua eficiência na representação de grafos esparsos. Para o caso de grafos densos as Matrizes de Adjacência são preferidas, isto porque o número de arestas E é aproximadamente igual ao número de vértices ao quadrado ou em casos que é necessário procurar rapidamente se existe uma aresta ligando dois vértices dados (CORMEN et al., 2001).
Obviamente visto que a i e a ii estão trocadas quanto a natureza dos grafos (esparso e denso) e sendo que não tem opção na avaliação para "nenhuma delas", apenas a iii está correta. Mas, vale lembrar que uma árvore não pode ser cíclica e tem de ter seus vértices conectados.
Resposta:
Explicação passo a passo: