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