c Balaji Raghavachari 121 Algorithm Design and Analysis c Balaji Raghavachari 122 Algorithm Design and Analysis Graphs concepts Paths and cycles G V E V is vertex set and E V V is edge set Undirected or directed Weighted or unweighted Simple or Multi a multigraph allows several edges between same two nodes and self loops A path P v0 v1 vk is a path of length k from u to v if v0 u vk v and vj 1 vj E for j 1 2 k Representation Adjacency list e cient Adjacency matrix Edge incidence matrix A cycle is a path in which v0 vk Path is simple if all its nodes are distinct A simple cycle is one in which v1 vk are distinct nodes For an edge u v E we say v is adjacent to u or v is neighbor of u If directed the edge goes from u to v When we say cycle path we usually mean only simple cycle path Degree of a vertex u is the number of its neighbors it has in G In directed graphs we have out degree number of outgoing edges from u in degree number of edges coming into u and degree sum of in degree and out degree of a vertex u c Balaji Raghavachari 123 Algorithm Design and Analysis Subpath of above path is vi vj where 0 i j k c Balaji Raghavachari 124 Algorithm Design and Analysis Components Acyclic graphs Nodes u and v are connected if there is a path from u to v in undirected graphs An acyclic undirected graph is called a forest A connected forest is called a tree Connected components of a graph are the equivalence classes of the connected relation between vertices A tree that connects all nodes of a graph is called a spanning tree A DAG is a directed acyclic graph In directed graphs u and v are strongly connected if there is a path from u to v and a path from v to u Directed or rooted tree a root node and directed edges that take you away from the root outgoing tree or toward the root incoming tree Strongly connected components of a directed graph are the equivalence classes of strongly connected relation between vertices c Balaji Raghavachari 125 Algorithm Design and Analysis c Balaji Raghavachari 128 Algorithm Design and Analysis Depth rst search DFS Subgraphs and morphisms DFS G for each vertex u V G do u Color W hite unvisited u P arent N il Initializations add more if needed time 0 Given G V E we say G V E is a subgraph of G if V V and E E Given G V E and a vertex set V V the graph G V E is an induced subgraph of G is E has all those edges of E that connected vertices of V G and G are isomorphic if there is a bijection f V V such that u v E f u f v E c Balaji Raghavachari 129 Algorithm Design and Analysis for each vertex u V G do if u Color W hite then DFS Visit u c Balaji Raghavachari Algorithm Design and Analysis Running time O E V DFS Visit u u Color Gray Being processed u dis time Discovery time of u Add other intializations as needed Active time period of a vertex u dis u n Parenthesis theorem for any two vertices u and v their active time periods are either disjoint or one is contained in the other for each v Adj u do if v Color W hite then v P arent u DFS Visit v 130 Properties of DFS DFS Visit u Color Black Done processing u u f in time Finish time of u If v is a descendant of u u dis v dis v f in u f in We say nodes x and y are unrelated if neither is a descendant of the other White path theorem At time u dis if v is reachable from u through a path of white nodes then v will be a descendant of u in the DFS tree c Balaji Raghavachari 131 Algorithm Design and Analysis c Balaji Raghavachari 132 Algorithm Design and Analysis Applications of DFS Topological sort Given a DAG directed acyclic graph G V E a topological ordering is a linear ordering of its vertices such that all edges of G go from left to right Classi cation of edges by DFS Undirected graphs Tree edges and Back edges There are no cross edges connecting two unrelated nodes Each vertex v is given a number top v such that whenever there is an edge u v then top u top v Directed graphs Observe that if G has a cycle then it can not have a topological ordering Tree edges from parent to child Back edges from descendant to ancestor Applications of topological sorting single processor scheduling of tasks with precedence constraints detecting deadlocks in operating syst and databases nding shortest paths in DAGs in linear time Forward edges non parent ancestor to descendant Cross edges from node u to unrelated node v only if v f in u dis c Balaji Raghavachari 133 Algorithm Design and Analysis DFS based algorithm order the vertices in the order of decreasing nish times c Balaji Raghavachari 134 Algorithm Design and Analysis Correctness of algorithm If u v E then top u top v Topological order Proof Edge u v is one of the following DFS Visit u topnum is a global variable initialized to V u Color Gray Being processed for each v Adj u do if v Color W hite then v P arent u DFS Visit v Tree edge v P arent u Therefore u nishes after v parenthesis theorem and hence u f in v f in Therefore top u top v since topnum is a monotonically decreasing variable Forward edge follows by using induction on previous case Back edge impossible since back edge implies cycle and G is acyclic toporder topnum u u top topnum u Color Black Done processing u Cross edge possible only if u dis v f in which implies that u f in v f in and therefore top u top v
View Full Document
Unlocking...