MO417 - Questão para a prova oral

Número: 065

Enunciado: Sobre estruturas para representação de grafos podemos afirmar que:

1. Tanto para grafos orientados quanto não orientados o uso de memória utilizando listas de adjacências é Theta(V+E).
2. Para grafos não orientados, a soma dos comprimentos das listas de adjacências é igual à metade da quantidade de arestas.
3. Grafos esparsos, aqueles que possuem número de vértices muito menor que o número de arestas são melhor representados utilizando listas de adjacências.
4. A representação por meio de uma matriz de adjacências exige Omega(|E|²) de memória.
5. NDA.

Autor(a): Rodrigo Tripodi Calumby