MO417 - Questão para a prova oral

Número: 2009-108

Enunciado: Sobre representação computacional de grafos, é INCORRETO afirmar que:

1. A representação por listas de adjacências tem a propriedade de que a quantidade de memória que ela exige é Θ(V+E), onde V é o numero de vértices e E o número de arestas. Todavia, esta propriedade só é válida para grafos não orientados.
   
2. A representação de grafos por listas de adjacências é vantajosa quando aplicada em grafos esparsos (número de arestas muito menor que o número de vértices ao quadrado), pois oferece uma representação compacta para esse tipo de grafo.
   
3. A representação de grafos por matriz de adjacências traz vantagens quando o grafo é denso (número de arestas próximo ao número de vértices ao quadrado) ou quando precisamos saber com rapidez se existe uma aresta conectando dois vértices dados.
   
4. A matriz de adjacências de um grafo não orientado é sempre igual à sua própria transposta (matriz simétrica). Desta forma, em algumas aplicações, pode compensar armazenar apenas as entradas contidas na diagonal e acima da diagonal da matriz, reduzindo assim quase pela metade a memória necessária para armazenar o grafo.
   
5. NDA

Ideia original de: Renato Hirata