Questão para a Prova Oral 151
Semana: 12/05/2003 a 16/05/2003
Assunto: Grafos 2 e Árvores esplalhadas Mínimas
Considerando o algoritmo DFS apresentado no livro, qual das
afirmativas abaixo é INCORRETA?
A) Para todo vértice v do grafo de entrada,
o tempo de início de exploração é estritamente
menor do que o tempo do término de exploração
B) Arestas de retorno não são encontradas porque
o algoritmo obtém florestas de profundidade, as quais
são formadas por árvores, e em árvores não pode
haver ciclos
C) O tempo de execução do algoritmo DFS é da ordem de
Theta(n+m), onde n é o número de vértices do grafo e
m é o número de arestas do grafo
D) Pode-se verificar as cores utilizadas pelo algoritmo
(BRANCO, CINZA, PRETO) durante a exploração dos vértices
para determinar a existência de ciclos no grafo de entrada
E) NDA
Autor: Augusto Jun Devegili
RA 025620