Past exam of the year 1 of the computer science course of the University of Oxford / 2017 / Functional programming, design and analysis of algorithms (resit) / 7

Maintain white, gray and black colors for undiscovered, active and completed vertices. A single traversal clock records DFS discovery and finishing times:

for v in V: color[v] = white; parent[v] = none
time = 0
visit(u):
    time = time+1; d[u] = time; color[u] = gray
    for v in adjacency[u]:
        if color[v] == white:
            parent[v] = u
            visit(v)
    color[u] = black; time = time+1; f[u] = time
for u in V:
    if color[u] == white: visit(u)

The outer loop makes a depth-first search forest even when the directed graph is disconnected. Each vertex is entered once and each directed adjacency entry is inspected once. Thus an adjacency list representation gives $O(|V|+|E|)$ time and $O(|V|)$ auxiliary storage, including the worst-case recursive stack. Sorting neighbors to impose a particular visit order would be additional work.

Relative to the resulting DFS edge classification, a tree edge in depth-first search discovers a white vertex and becomes its parent edge. A forward edge in depth-first search goes to a proper descendant but is not that descendant's discovery edge. A back edge in depth-first search goes to an active ancestor, with a self-loop also counted as a back edge when such edges are allowed. A cross edge in depth-first search joins vertices with no ancestor-descendant relationship in the forest, such as different completed branches or different trees.

The definitions refer to directed edges; an undirected graph is normally classified only with tree and back edges, accounting for the reverse copy of a parent edge separately.

False. Use vertices $x,u,v$, edges $x\to u$, $u\to x$, $x\to v$, and start depth-first search at $x$, scanning $u$ before $v$. The times areThere is a directed path $u\to x\to v$ and $d(u)<d(v)$, but $u$ and $v$ are separate children of $x$. Thus $v$ is not a descendant of $u$. The path leaves $u$ through an already gray ancestor; its later branch need not be explored inside $u$'s recursive call. This is consistent with the DFS parenthesis property.

False. The same ordered traversal gives a path $u\to x\to v$, butA path from $u$ can pass through an already discovered ancestor, whose remaining edges are scanned only after $u$ finishes. A reachability statement alone therefore does not impose the claimed finishing-time bound.

True for a directed cycle. Suppose there were no back edges. On examining an edge $u\to v$, its target would either be white, in which case its recursive call finishes before $u$; or black, in which case it has already finished. A gray target would be an active ancestor and hence give a back edge, contrary to the supposition. Therefore every edge would satisfy $f(v)<f(u)$.

Applying those strict inequalities around a directed cycle would imply $f(u)<f(u)$, a contradiction. Thus some back edge in depth-first search must exist in the search's edge classification. Such an edge is classified relative to the DFS forest; it is not one of the forest's tree edges.

False. Take edges $u\to a$ and $c\to u$, and let the outer DFS loop try vertices in order $a,u,c$. The first call finishes $a$ immediately. The next discovers $u$, whose only outgoing edge reaches already black $a$, so its tree contains only $u$. Finally $c$ sees already black $u$.

Vertex $u$ has both an incoming edge from $c$ and an outgoing edge to $a$, yet is the sole vertex of its DFS tree. Nonzero incoming and outgoing degrees do not require either edge to become a tree edge in depth-first search.