2
$\begingroup$

Studying for my finals. So I'm reading the "Introduction to Algorithms (Third Edition)" book. In the DFS section there is the following section:

Depth-first search yields valuable information about the structure of a graph. Perhaps the most basic property of depth-first search is that the predecessor subgraph $G_{\pi}$ does indeed form a forest of trees, since the structure of the depth-first trees exactly mirrors the structure of recursive calls of DFS-VISIT. That is, $u=v.\pi$ if and only if DFS-VISIT(G,v) was called during a search of $u$’s adjacency list. Additionally, vertex $v$ is a descendant of vertex $u$ in the depth-first forest if and only if $v$ is discovered during the time in which $u$ is gray.

I'm trying to prove the following statement for myself:

In every DFS run on $G$, in every step of DFS, the $G_{\pi}$ is a forest.

This question is coming from a booklet published for studding for the finals (without solutions).

I understand the logic behind why it true (with the help of the statements from the book). But I struggle of writing a "formal proof" which shows the correctness of it. Do I need to use induction to prove it (since I need to show it for every step). How to prove this statement formally?

For the completeness of the question, the $G_\pi=(V,E_\pi)$ is the following graph: $$ E_\pi=\{(\pi[v],v)\,:\,\pi[v]\neq NULL \wedge v\in V\} $$

$\endgroup$

1 Answer 1

2
$\begingroup$

Yes use induction. You will assume that $G_\pi$ is a forest, and you want to prove that $G_{\pi'}$ is also a forest, where $\pi'$ is $\pi$ after one step of the DFS algorithm.

The key point, is that a forest is a graph without cycles. So basically, you want to show that no new cycles where created in the last step. To prove this, you will want to have a statement similar to this:

Assume towards contradiction that $G_{\pi'}$ contains a cycle. Hence, the new node $u'$ that was added to $G_{\pi}$ in order to create $G_{\pi'}$ must be a part of the new cycle (since $G_{\pi}$ was a forest). Therefore, there must be some node $u\in G_\pi$ such that $\pi(u)=u'$, but this is impossible since it would mean that $u'$ would have been already visited in $G_{\pi}$, but this is impossible since $u'$ was visited only after $G_{\pi}$ was constructed.

$\endgroup$
4
  • $\begingroup$ Thank you! If $G_\pi$ does not have cycles, it means that it's a forest or I need to add something after that? $\endgroup$
    – vesii
    Jul 25, 2021 at 12:28
  • $\begingroup$ A tree is a connected acyclic graph. A forest, is just like a tree, but it doesn't have to be connected. Therefore, a forest is just an acyclic graph $\endgroup$
    – nir shahar
    Jul 25, 2021 at 12:49
  • $\begingroup$ Ok got it. Another last question - for the base of the induction, can I say the following? - Base: for $k=0$ (where $k$ is the DFS step), the graph $G_\pi$ consists of $|V|$ vertices with no edges so each vertex is a tree and $G_\pi$ is a forest consisting of $|V|$ trees. $\endgroup$
    – vesii
    Jul 25, 2021 at 13:05
  • $\begingroup$ @vesii yes, that is totally valid $\endgroup$
    – nir shahar
    Jul 25, 2021 at 13:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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