Algorithms Notes – Chapter 10

Obligatory Computer Science Comic

Depth-First Search – Analysis (continued)

White Path Theorem

Theorem: Let G be a directed or undirected graph on which a depth-first search is executed. Let u and v be two vertices in G. v is a descendant of u if and only if at the time u.d when the algorithm discovers u, there is a path from u to v that consists entirely of white vertices.

Proof: Since this is an if-and-only-if theorem, we must prove both sides of the implication.

Proof of \Rightarrow: Suppose v is a descendant of u in the depth-first forest. By corollary 1 (from the last chapter), we know that u.d < v.d. So v is not discovered before u is discovered, hence v is white at time u.d. Since v can be any descendant of u, all vertices in the unique simple path from u to v in the depth-first forest must be white at time u.d. In the case that v = u, the path just contains the vertex u which is still white when the value of u.d is set by the algorithm.

Proof of \Leftarrow: Suppose there is a path containing only white vertices from u to v at time u.d and v does not become a descendant of u. Let v be the closest non-descendant vertex to u in the path. Let w be the predecessor of v. Since v is the closest non-descendant vertex to u, w is a descendant of u. By corollary 1 from the last chapter, we know that w.f \le u.f (and w.f = u.f if u and w are the same vertex). Since v is a descendant of w, it must be discovered after u is discovered and before the adjacency list scan of w is finished. Hence, it must be true that u.d < v.d < w.f < u.f. The parenthesis theorem then implies that [v.d, v.f] is contained entirely within the interval [u.d, u.f]. By corollary 1, this means that v is still a descendant of u. \square

Note: A depth-first forest is often denoted by G_{\pi} by convention. Just like we denote a graph as G and vertices as u and v. Not necessary at all, just a convention.

math_paper

xkcd/410

G_{\pi} Edge Classification

We can use a depth-first forest to classify edges into four types:

  1. Tree Edges – Let v be a vertex discovered by a DFS. If v was first discovered by exploring any edge (u, v) then that edge is a tree edge. (i.e the edges that are part of a depth-first forest G_{\pi}.
  2. Back Edges – Let u and v be vertices in a depth-first tree such that u is a descendant of v. An edge (u, v) connecting u to its ancestor v is a back-edge. In a directed graph, a self-loop is also a back-edge.
  3. Forward Edges – Non-tree edges that connect two vertices u and v such that v is a descendant of u in a depth-first tree.
  4. Cross Edges – All edges that are not tree edges, back edges or forward edges (i.e an edge that is not in any of the above three categories is a cross edge).

Let (u, v) be an edge explored by the depth-first search algorithm. The color of the vertex v indicates the type of edge (u, v) is:

  1. White – tree edge
  2. Gray – back edge
  3. Black – forward or cross edge

Note: I do not understand the proof of this relation between vertex color and type of edge properly myself. The book doesn’t deal with it very formally, in my opinion. Anyway, onto the next theorem.

Theorem 2: Let G be any undirected graph. In a depth-first search of G, every edge of G is either a tree edge or a back edge.

Proof: Let (u, v) be any edge in G. Suppose u.d < v.d (without loss of generality). Then before the algorithm finishes u, it must discover and finish v while the color of u remains gray, since v is in the adjacency list of u. If the direction of the edge (u, v) is from u to v the first time the algorithm explores it, then the vertex v has not been discovered before that time. This is true because if it had been discovered previously, the algorithm would have already explored the edge (u,v ) in the direction from v to u.

Since, at the time (u, v) is first explored, v is undiscovered, its color is white. Hence (u, v) becomes a tree edge. If the algorithm explores (u, v) first in the direction from v to u instead then, since the color of u is gray, the edge (u, v) becomes a back edge. \square

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s