Graphs Part 7 Classification of Edges by DFS Tree edges An edge u v is in a tree edge if v is discovered by exploring edge u v Back edges are those edges u v connecting a vertex u to an ancestor v in a depth first tree A self loop edge is considered as a back edge Classification of Edges by DFS Forward edges are non tree edges u v connecting a vertex u to a descendant v in a depth first tree Cross edges are all other edges Classification of Edges directed graph a 1 8 6 7 x b 2 5 3 4 y c 9 12 10 11 z Tree Edges Back Edges a x a x b y b y c z c z a x a x b y b y c z c z Forward Edges Cross Edges Classification of Edges undirected graph a 1 12 3 10 x b 2 11 4 9 y c 5 8 6 7 z Theorem In a DFS of an undirected graph G for each undirected edge u v we have either 1 u v or v u is first traversed as a tree edge or 2 u v or v u is first traversed as a back edge Tree Edges Traversed a b before b a Back Edges Traversed x a before a x a x a x b y b y c z c z a x a x b y b y c z c z Forward Edges Cross Edges The Case of Undirected Graphs In a DFS of an undirected graph every edge is either a tree edge or a back edge Why Let u v be an arbitrary edge in the graph WLOG assume that u d v d This means that when u turns GRAY v is still WHITE Since u v is an edge v will turn GRAY while u is still GRAY Therefore the search must discover and finish v before it finishes u The Case of Undirected Graphs Therefore the search must discover and finish v before it finishes u If u v is first explored from u u v is a tree edge a b in the example is such an edge If u v is first explored from v u v is a back edge a x in the example is such an edge Illustration a 1 12 3 10 x b 2 11 4 9 y c 5 8 6 7 z a x b y c z a x b y c z Tree Edges Traversed a b before b a Back Edges Traversed x a before a x Nesting of Descendants Intervals Theorem Vertex is a proper descendant of vertex in the DFS forest if and only if Proof It follows from the DFS algorithm the set are 2n distinct positive integers 1 2 2 1 2 Assume that is a proper descendent of Then is WHITE when turns GRAY and turns GRAY then BLACK when is still GRAY Hence we have Assume that Then turns GRAY when is GRAY and turns BLACK while is still GRAY Hence is a proper descendent of White path Theorem Theorem In a DFS forest of a directed or undirected graph G V E vertex is a descendant of vertex if and only if at the time that the search discovers there is a path from to consisting entirely of white vertices Proof This follows directly from the DFS algorithm Parenthesis Theorem Theorem In any depth first search of a directed or undirected graph G V E for any two vertices u and v exactly one of the following three conditions holds the intervals u d u f and v d v f are entirely disjoint and neither u nor v is a descendant of the other in the depth first forest the interval u d u f is contained entirely within the interval v d v f and u is a descendant of v in a depth first tree or the interval v d v f is contained entirely within the interval u d u f and v is a descendant of u in a depth first tree Parenthesis Theorem Proof Without loss of generality assume that Hence when turns GRAY is still WHITE We consider two disjoint cases 1 there is a WHITE path from to 2 there is no WHITE path from to In case 1 will turn GRAY before turns BLACK Hence we have is a descendent of In case 2 remains WHITE when turns BLACK Hence we have Neither is a descendent of the other Summary Classification of Edges Tree Back Forward Cross White Path Theorem Parenthesis Theorem Graphs Part 8 Cycle in a Directed Graph A cycle in directed graph without edges from and to the same vertex G V E is a sequence of two or more vertices v1 v2 vk such that vi vi 1 E for i 1 2 k 1 and vk v1 E A self loop is considered a cycle An example graph is given on this page a b d is a cycle a d b e c f Cycle in a Directed Graph A cycle in directed graph without edges from and to the same vertex G V E is a sequence of two or more vertices v1 v2 vk such that vi vi 1 E for i 1 2 k 1 and vk v1 E A self loop is considered a cycle An example graph is given on this page a b d is a cycle a b e d is a cycle b c a d e f Finding a Cycle in a Directed Graph If there is a back edge we have a cycle If there is a cycle there is a back edge c 9 12 a 1 8 4 5 x b 2 7 3 6 y F B C B 10 11 z B 4 5 x b 2 7 3 6 y Directed Acyclic Graph DAG A directed graph is called a DAG directed acyclic graph if it does not contain a cycle A DAG is given on this page a d b e c f Topological Sort of a DAG A topological sort of a DAG G V E is an ordering of the vertices v1 v2 vn such that vi vj E implies i j Examples a b c e d f a c f b e d Topological sort is not unique a d b e c f Computing a Topological Sort of a DAG Topological Sort G 1 call DFS G to compute finishing times v f for each vertex v as each vertex is finished insert it onto the front of a linked list 2 3 Return the linked list of vertices NOTE We can replace the linked list with a stack Computing a Topological Sort of a DAG We consider two cases when the edge u v is explored If G is a DAG Topological Sort G produces a topological sort of G Proof If u v is an edge then 1 v is WHITE 2 v is BLACK Computing …
View Full Document
Unlocking...