Question

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.​

Answer 1

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 $V^{2}$   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.

Answer 2

Resposta:

Explicação passo a passo: