mig2

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Dado as afirmações abaixo sobre algoritmos em grafos (considerando um grafo por G(V,E), onde V é o número de vértices e E o número de arestas )

I. A árvore BFS de um grafo é única.
II. A análise agregada do algoritmo BFS resulta em uma complexidade Θ(V+E).
III. Uma ordenação topológica não pode ser resolvida por DFS.
IV. Trabalhar com matrizes de adjacência é mais vantajoso do que com listas de prioridade.
V. A multiplicação da matriz de adjacência por ela mesma fornece o grafo complementar (GT(V,E)) do original, sendo G(V,E) direcionado.

A alternativa que representa as afirmações incorretas é:

a) I, II, III, IV, V
b) I, II , III, V
c) I, III , IV
d) I, II, IV
e) NDA.



Ideia original de: Lucas Miguel de Carvalho