jun

MO417 - Questão para a prova oral

Numero:

Enunciado: Leia a seguintes afirmações e assinale a alternativa Correta

I     Num grafo  esparso (Sparse graph) o numero de arestas | E | é muito menor do que o numero de vértices | V | ^ 2 ,  num grafo denso(graph is dense) o numero de arestas | E | esta próximo do numero de | V | ^2.
II    Quando o numero de arestas | E | é muito menor do que o numero de vértices | V | ^ 2 eu devo utilizar a representação de lista de adjacências(Adjacency-list representation) de um grafo G= (V, E).

III   Quando o numero de arestas | E | esta próximo do numero de | V  | ^2 eu devo utilizar a representação de matriz de adjacências(Adjacency-matrix representation) de um grafo G = (V,E).

IV   A representação de listas de adjacência de um grafo G exige uma quantidade de memoria o qual  é Θ ( V + E ) . E a  representação de matriz de adjacência de um grafo G precisa de Θ ( V^2 ) em memoria.

V    Seja G= (V , E) um grafo orientado ou não orientado , e seja s ∈ V um vértice arbitrário, então para qualquer aresta  ( u ,v) ∈ E  , A distancia do caminho mais curto de s a v é maior o igual do que a distancia do caminho mais curto de s a u mais um (&(s,v) >= &(s,u) + 1).

Qual é a alternativa correta:

a) Somente I , II , III e IV são corretas

b) Somente I , II e III são corretas

c) Somente I , II , III , IV e V são corretas

d) Somente I , IV são corretas

e) NDA

                                             Ideia original de: Junior Cupe Casquina