Questão para a Prova Oral 138

Semana: 05/05/2003 a 09/05/2003
Assunto: Conjuntos Disjuntos e Grafos I


Indique a quantidade de memória exigida para representarmos um grafo G=(V,E), como uma “lista de adjacências” e como uma “matriz de adjacências”, respectivamente:

A) Theta(V + E) e Theta(V^2);
B) Theta(V^2) e Theta(V + E);
C) Theta(V + E) e Theta(V + E);
D) Theta(V^2) e Theta(V^2);
E) n.d.a.

Autor: Carlos Senna
RA: 022.248