DFS Parentheses Theorem

Edit the RMarkdown source file for this assignment in RStudio. When you finish, Knit the file to HTML and upload the .html output to Canvas.

For this assignment, we will use the following version of depth-first search.

DFS(v, clock):
    mark v
    clock <- clock + 1; v.pre <- clock
    for each edge vw
        if w is unmarked
            w.parent <- v
            clock <- DFS(w, clock)
    clock <- clock + 1; v.post <- clock
    return clock

Suppose the DFS algorithm is called on the following graph as DFS(v1, 0). When a vertex v has more than one outgoing edge vw, assume that the for-loop considers the vertices w \(=v_i\) in order of subscript.

1. Give the discovery time v.pre and finish time v.post for each vertex.

2. Use ASCII art to create a number line figure illustrating the active intervals for each vertex, like the one in Figure 6.4 on p. 229 of [E]. (The interval for v1 is done for you.)

[-------------------------v1-----------------------]





1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20

3. Classify each edge as tree edge, forward edge, back edge, or cross edge.

4. List the vertices in the order of a preorder traversal and also in the order of a postorder traversal.

5. Find two vertices \(v_i\) and \(v_j\) such that the trees produced by DFS(v_i,0) and DFS(v_j,0) overlap, but in a way such that neither tree is contained in the other.