1.) (25 points) Perform a depth-first search on each of the following graphs; whenever there’s a choice of multiple vertices, pick the one that is alphabetically first.
(a.) Classify each edge in Graph X as a tree edge, forward edge, back edge, or cross edge.
Solution:
(b.) Give the pre and post number of each vertex in Graph X.
(c.) Classify each edge in Graph Y as a tree edge, forward edge, back edge, or cross edge.
(d.) Give the pre and post number of each vertex in Graph Y .
Solution:
2.) (25 points) Run the DFS-based topological ordering algorithm on the following graph. When-ever you have a choice of vertices to explore, always pick the one that is alphabetically first.
(a.) Indicate the pre and post numbers of the vertices.
Solution:
(b.) What are the sources and sinks of the graph?
Solution:
(c.) What topological ordering is found by the algorithm?
Solution:
(d.) How many topological orderings does this graph have?
3.) (25 points) Run the strongly connected components algorithm on the following directed graphs. When running DFS for this problem, if there is a choice of vertices to explore, always pick the oe that is alphabetically first.
(a.) In what order are the strongly connected components (SCCs) found for Graph X?
Solution:
(b.) Which are source SCCs and which are sink SCCs for Graph X?
Solution:
(c.) Draw the “metagraph” of Graph X (each meta-node is a SCC of Graph X).
Solution:
(d.) What is the minimum number of edges you must add to Graph X to make it strongly connected?
Solution:
(e.) In what order are the strongly connected components (SCCs) found for Graph Y ?
Solution:
(f.) Which are source SCCs and which are sink SCCs for Graph Y ?
Solution:
(g.) Draw the “metagraph” of Graph Y (each meta-node is a SCC of Graph Y ).
Solution:
(h.) What is the minimum number of edges you must add to Graph Y to make it strongly connected?
Solution:
4.) (25 points) Let G = (V, E) be a directed graph for which you have an adjacency list. A vertex v is called a global sink if and only if it meets the following two conditions:
1. v has no outgoing edges
2. for every other vertex u, there is a path from u to v
Give an algorithm that determines if G has a global sink and, if the answer is yes, returns the global sink. Your algorithm should have running time O(|V | + |E|).
Solution:
