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 / c

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.