tia

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Sobre os grafos, seus algoritmos e seus tipos de representações, podemos afirmar:

I - O custo total de execução tanto do BFS quanto do DFS independe do tipo de representação (lista ou matriz) do grafo.
II - O DFS é usado, entre outras coisas, para ordenação topológica e para achar as componentes fortemente conectadas.
III - O custo total do BFS e do DFS é theta(V + E) somente quando o grafo é representado por uma lista de adjacências.
IV - Um grafo pode ser representado ou por uma lista de adjacência ou por uma matriz de adjacência dependendo de qual otimização é necessária.

Dentre as afirmações acima, qual ou quais NÃO são verdadeiras:

A) I, somente

B) I, II e IV, somente

C) III, somente

D) I e III, somente

E) N.D.A.

Ideia original de: Tiago Pedroso da Cruz de Andrade