- vertex set = {A, B, C, D, E, F, G, H, J}

- directed edges = { (A,B), (A,C), (B,D), (B,E), (D,H), (D,J), (C,F), (C,G), (H,B), (D,A), (F,E), (A,G) }

Start the DFS at vertex A, and, given a choice, visit neighbors of each vertex in alphabetical order.

Recall that the dfs-numbering of the vertices gives the order in which the vertices are first encountered during the DFS.

Define the *dfs post-order numbering* of the vertices so that it gives the order
in which the vertices are first *finished with* during the DFS.

For example, a vertex v has post-order number 1 if it is the first one such that the call DFS(v) returns. (Such a vertex will always be a leaf in the dfs tree.) The vertex with post-order number N (the number of vertices) will always be the root of the DFS tree, provided all vertices are reachable from the root.

1A. What are the dfs-numbers of the vertices?

1B. What are the dfs-post-order numbers of the vertices?

1C. If you run BFS (breadth-first search, starting at A) what are the distance labels of the vertices?

vertex: | A | B | C | D | E | F | G | H | J |

dfs-number: | 1 | 2 | 7 | 3 | 6 | 8 | 9 | 4 | 5 |

post-order: | 9 | 5 | 8 | 3 | 4 | 6 | 7 | 1 | 2 |

distance: | 0 | 1 | 1 | 2 | 2 | 2 | 1 | 3 | 3 |

*
*

Recall that DFS on a directed graph classifies edges into
*tree*,
*back*,
*cross*,
and *forward* edges.

2A. List the edges of each type in the example you did above.

2B. In general, if an edge (u,v) is of the type in the first column below, which conditions are possible?

2A.

- tree: (A,B) (A,C) (B,D) (B,E) (C,F) (C,G) (D,H) (D,H)
- back: (D,A) (H,B)
- cross: (F,E)
- forward: (A,G)

2B.

*
*

Run [Dijkstra's algorithm] on the following directed graph, starting at vertex 1. After each iteration of the outer loop, show the contents of the queue Q (the vertices in the queue and their keys). What are the final distances (in the distance[] array)?

*
*

- iteration 0: Q={vertex 1 with key 0}
- iteration 1: Q={vertex 2 with key 10, vertex 3 with key 50, vertex 4 with key 65} (distance[1] = 0)
- iteration 2: Q={vertex 3 with key 40, vertex 4 with key 65, vertex 5 with key 14} (distance[2] = 10)
- iteration 3: Q={vertex 3 with key 40, vertex 4 with key 65} (distance[5] = 14)
- iteration 4: Q={vertex 4 with key 63} (distance[3] = 40)
- iteration 5: Q={} (distance[4] = 63)

4A: Give an example of a graph with 5 vertices (two of which are S and T) with three S,T-cut vertices.

*
*

S--a--b--c--T

4B: prove or disprove the following claim: In a DFS of the graph starting at S, every S,T-cut vertex must lie on the path from S to T in the resulting dfs tree.

*Claim is true. Suppose a vertex v does not lie on the path. Then even if v is removed,
there remains a path from S to T. Thus v is not an S,T-cut vertex.
*

4C: prove or disprove the following claim: In a DFS of the graph starting at S, every vertex on the path from S to T in the resulting DFS tree is an S,T-cut vertex.

*Claim is false. Consider for example a cycle or a complete graph on at least 3 vertices.
These graphs have no S,T-cut vertices.
*

4D: use low[] numbers (from the DFS-based alg for finding cut vertices) to give a necessary and sufficient condition for a vertex W on the path from S to T in the DFS tree to be an S,T-cut vertex.

*
*

*
A vertex v (other than S or T) on the S,T-path in the DFS tree
is an S,T-vertex iff
it has a child w in the DFS tree that
is on the path from S to T and has low[w] ≥ dfs-num[v].
*

*
Note that this includes the case when v is the lowest common
ancestor of S and T (when neither S, nor T is the root of the DFS tree).
*