vla

MO417 - QUESTÃO PARA A PROVA ORAL
Número:
Seja o grafo orientado G=(V,E) da figura, em que |V|=n e |E|=k1+k2
k1 numero de arestas multiplas (vi <---> vj)
k2 numero de arestas simples (vi--->vj ou vi<---vj).

Se G é representado por meio de listas de adjacência. Pensar em um algoritmo para converter o grafo G em G' tal que as listas de adjacência de G’ sejam equivalente às listas de adjacência da versão não orientado do grafo G.

Quantas inserções em listas devem ser feitas e quais a complexidade do algoritmo?

a. 2k1  e  O(V+E)
b. 2(k1+k2)  e  O(V+k1)
c. k2  e  O(V+E)
d. k1+k2  e  O(V+k2)
e. DNA

Ideia original de: Vladimir Jaime Rocca Layza