算法课件Lecture3章节.pptVIP

Properties of DFS (Cont.) Parenthesis Theorem: In any DFS of a graph, for each pair of vertices u, v, exactly one of the following conditions holds: u is a descendant of v, and [d[u], f[u]] is a subinterval of [d[v], f[v]]. u is an ancestor of v, and [d[v], f[v]] is a subinterval of [d[u], f[u]]. Neither u is a descendant of v nor v is a descendant of u, and [d[u], f[u]] and [d[v], f[v]] are disjoint. Page:166 Proof It is obvious that each pair u,v satisfies exactly one of the following: u is a descendant of v v is a descendant of u neither is descendant of the other It is enough to prove that 1 holds if and only if 1 [d[u], f[u]] is a subinterval of [d[v], f[v]]; 2 holds if and only if [d[v], f[v]] is a subinterval of [d[u], f[u]]; 3 holds if and only if [d[u], f[u]] and [d[v], f[v]] are disjoint. Proof (Continued) If 1 holds, then u must be discovered when v is gray, that means d[v]d[u]f[u]f[v]. In the opposite, if d[v]d[u]f[u]f[v], then u is discovered when v is gray, that is, u is a descendant of v. Then second case is similar to the above. If neither is descendant of the other. Without loss of generality, suppose d[u]d[v], then, since v is not a descendant of u, v must be discovered after u finishes, that is, f[u]d[v], hence, [d[u], f[u]] is disjoint with [d[v],f[v]]. In the opposite, if [d[u],f[u]] and [d[v],f[v]] are disjoint, then neither is discovered when the other is gray, so, neither is descendant of the other. Nesting of descendants’ intervals Corollary: vertex v is a proper descendant of vertex u in the depth-first forest for a graph G if and only if d[u] d[v] f[v] f[u]. White-path theorem Theorem: In a depth-first forest of a graph G = (V, E), vertex v is a descendant of u if and only if at time d[u], vertex v can be reached from u along a path consisting entirely of white vertices. Proof of White-path theorem =Assume v is a descendant of u, there is a unique path from u to v in the DFS forest. Suppose w is an arbitrary vertex on the pat