0
$\begingroup$

Question: Consider the DFS tree generated by a DFS on a connected graph. Write below the necessary and sufficient condition for a node v to be a leaf node on the DFS tree. The condition must be in term's of v's discovery time d[v] and finishing time f[v].


I honestly have no idea what the answer to this question from a past exam may be...

$\endgroup$
1
$\begingroup$

A node v is a leaf node on the DFS tree if and only if f[v] = d[v] + 1.

The proof is obvious once you follow the DFS, marking each node's discovery time and finishing time. A leaf is defined as a node that has no children. Let $v$ be a node.

  • Suppose $v$ has children in the final DFS tree. That is, we will go forward to a child $u$ of $v$ right after we have discovered $v$. That is, $d[v]+1 = d[u]$. The finishing time of $v$ must come after that. So f[v] $\gt$ d[v] + 1.
  • Suppose $v$ has no children in the final DFS tree. That is, we will go backtracking once we have discovered $v$. That is, we will finish $v$ right after we have discovered it. That is, f[v] = d[v] + 1.

For people who are not familiar with discovery time and finishing time of a node v associated to a DFS, you can check either Stanford course note or Carnegie Mellon course note. Of course, you may just search by yourself.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.