MO417 - Questão para a prova oral

Número: 2013-062

Enunciado: Suponha que numa busca em profundidade (depth-first search) os nós recebem cores segundo o seguinte esquema:
BRANCO - nunca foi visitado
CINZA - já foi visitado, mas sua sub-árvore ainda não foi totalmente explorada
PRETO - sua sub-árvore já foi totalmente explorada

Ao encontrar uma aresta (u,v) durante a busca, quais das afirmações abaixo são corretas?

I - Se v estiver BRANCO, (u,v) será uma aresta de árvore (tree edge)
II - Se v estiver CINZA, (u,v) será uma aresta de cruzamento (cross edge)
III - Se v estiver PRETO, (u,v) será uma aresta de cruzamento (cross edge) ou uma aresta de avanço (forward edge), em grafos orientados, e tal situação não ocorre em grafos não-orientados

a. apenas I
b. apenas II
c. I e II
d. II e III
e. NDA

Ideia original de: Jorge Augusto Hongo