MO417 - Questão para a prova oral

Número: 2013-071

Enunciado: Considere uma busca em profundidade no seguinte grafo orientado, supondo que vértices são processados em ordem alfabética e que as listas de adjacência também estão em ordem alfabética:

Qual das seguintes afirmações é correta?

a) A busca resulta em 3 "DFS trees", 7 "cross edges", 1 "back edge" e pode ser ordenado topologicamente.
b) A busca resulta em 3 "DFS trees", 7 "cross edges", 1 "back edge" e não pode ser ordenado topologicamente.
c) A busca resulta em 3 "DFS trees", 1 "cross edges", 7 "back edge" e não pode ser ordenado topologicamente.
d) A busca resulta em 3 "DFS trees", 1 "cross edges", 7 "back edge" e pode ser ordenado topologicamente.
e) NDA.

Ideia original de: Carlos Eduardo Alfaro Morales