MO417 - Questão para a prova oral

Número: 2010-068

Enunciado: Considere o grafo orientado a seguir, onde será realizada uma busca em profundidade partindo-se do vértice de cor branca. Durante a busca, gera-se uma floresta de busca em profundidade e classificam-se as arestas como segue:
I) Arestas de Árvore (que fazem parte de uma árvore de busca em profundidade).
II) Arestas Diretas (que ligam um ancestral a um descendente).
III) Arestas de Retorno (que ligam um descendente a um ancestral).
IV) Arestas Cruzadas (as demais).

Mesmo sem saber a ordem em que alguns vértices serão visitados, pode-se ter certeza que o algoritmo encontrará durante o percurso, PELO MENOS:

1. 1 Aresta de Retorno e 2 Arestas Cruzadas
2. 1 Aresta Direta, 1 Aresta Cruzada e 1 Aresta de Retorno
3. 1 Aresta Cruzada e 2 Arestas de Retorno
4. 8 Arestas de Árvore
5. NDA

Ideia original de: Ewerton Almeida Silva