MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-067

Enunciado: Execute uma busca em profundidade no grafo abaixo, supondo que as listas de adjacências estejam em ordem alfabética. Toda vez que for reiniciá-la, pegue o primeiro vértice em ordem alfabética que ainda não foi visitado. Com base na classificação das arestas da busca em profundidade, pode-se dizer que o algoritmo encontrará durante o percurso:

Lembrete: 

I) Aresta de Árvore: faz parte de uma árvore de busca em profundidade;

II) Aresta de Retorno: liga um descendente a um ancestral;

III) Aresta Diretas: liga um ancestral a um descendente que não seja filho;

IV) Arestas Cruzadas: as demais.

a) 7 Arestas de Árvore e 2 Arestas de Retorno
b) 2 Arestas Diretas e 2 Arestas Cruzadas
c) 8 Arestas de Árvore e 1 Arestas de Retorno
d) 2 Arestas Diretas e 3 Arestas Cruzadas
e) NDA 
 

Ideia original de: Ademar Takeo Akabane