Exercícios

 

1 - Qual a sequência de vértices visitados numa travessia em profundidade primeiro (DFS) sobre o grafo abaixo, com origem no vértice A ? Considere que os vértices são visitados por ordem alfabética e que os vértices adjacentes de um vértice também são visitados por ordem alfabética.

dfs1 

2 - Considere uma travessia em profundidade primeiro (DFS) do grafo abaixo, com origem em A, e na qual os vértices são visitados por ordem alfabética e os vértices adjacentes de um vértice também são visitados por ordem alfabética. Indique os arcos de árvore, arcos para trás, arcos para a frente e arcos de cruzamento. 

dfs2 

3 - Considere uma travessia em profundidade primeiro (DFS) sobre o grafo abaixo, com origem no vértice A. Considere ainda que os vértices são visitados por ordem alfabética e que os vértices adjacentes de um vértice são também visitados por ordem alfabética. Qual o número de arcos para trás e de cruzamento que resultam da execução desta travessia? 

dfs3 

4 - Qual a sequência de vértices visitados numa travessia em largura primeiro (BFS) sobre o grafo abaixo, com origem no vértice A ? Considere que os vértices são visitados por ordem alfabética e que os vértices adjacentes de um vértice também são visitados por ordem alfabética. 

bfs1 

5 - Qual das sequências de vértices corresponde a uma ordenação topológica do grafo abaixo ? 

ot1 

a. <A,B,C,D,E,F,G> 
b. <B,A,D,C,G,F,E> 
c. <B,A,D,F,E,G,C> 
d. <B,F,A,E,D,C,G> 
e. <C,G,E,B,A,D,F> 
f. <F,E,G,D,C,B,A> 
g. <F,G,E,B,A,D,C> 

6 - Qual o número de componentes fortemente ligados do grafo dirigido da figura abaixo? 

scc1