8150.graphs

1. Graphs Steve Paks

2. Index The Graph Abstract Data Type Elementary Graph Operations Minimum Cost Spanning Trees Shortest Paths and Transitive Closure Activity Networks

3. Curriculum Model CS A A A A CS A A A A A CS : Computer Science A : Application Java Language Base Here I am

4. The Graph Abstract Data Type Introduction Analysis of electrical circuits finding shortest routes project planning identification of chemical compounds all mathematical structures

5. The Graph Abstract Data Type(Cont’d) Definitions A graph consists of nonempty set of vertices empty set of edges G = (V, E) undirected graph ( v , v 1 ) and ( v 1 , v ) represent the same edge directed graph < v , v 1 > represents an edge in which v is the tail and v 1 is the head

6. The Graph Abstract Data Type(Cont’d) Definitions(Cont’d) Restriction on Graphs A graph may not have self loops A graph may not have multiple occurrences of the same edge A complete graph having the maximum number of edges undirected graph = n(n-1)/2 directed graph = n(n-1) Adjacent Ex) in Graph G 2 – vertices 3, 4 and 0 are adjacent to vertex 1 incident on Ex) in Graph G 2 – edges (0, 2), (2, 5) and (2, 6) are incident on vertex 2 directed edge< v , v 1 > Adjacent – v is adjacent to v 1 , v 1 is adjacent from v incident on - < v , v 1 > in incident on v and v 1 Ex) in Graph G 3 – edges<0, 1>, <1, 0> and <1, 2> are incident on vertex 1

7. The Graph Abstract Data Type(Cont’d) Definitions(Cont’d) Subgraphs A subgraph of G is a graph G` such that V(G`) ⊆ V(G) Ex) Subgraphs of G 1 the length of path the number of edges on a path simple path a path in which all vertices, except the first and the last, are distinct Ex) (0, 1), (1, 3), (3, 2) can be written as 0, 1, 3, 2 in graph G 1 0, 1, 3, 2 is a simple path, while 0, 1, 3, 1 is not. Cycle a simple path in which the first and the last vertices are the same Ex) in Graph G 1 0, 1, 2, 0 is a cycle

8. The Graph Abstract Data Type(Cont’d) Definitions(Cont’d) Connected in an undirected graph G, two vertices, v and v 1 , are connected in the case of v and v 1 has a path Ex) graph G 1 and G 2 are connected, while graph G 4 is not Connected component Graph G 4 has two components, H 1 , H 2 Strongly connected for a directed graph

9. The Graph Abstract Data Type(Cont’d) Definitions(Cont’d) Degree the number of edges incident to that vertex e =( )/2(e edges, n vertices, d i is the number of a vertex i ) Ex) the degree of vertex 0 in G 4 is 2 in-degree the number of edges for vertex v as the head Ex) vertex 1 has in-degree 1 in graph G 3 out-degree the number of edges for vertex v as the tail Ex) vertex 1 has out-degree 2 in graph G 3  

10. The Graph Abstract Data Type(Cont’d) Definitions(Cont’d) ADT Graph

11. The Graph Abstract Data Type(Cont’d) Graph Representation Adjacent Matrix two-dimensional array( adj_mat [][]) the edge (v i , v j ) adj_mat [ i ][j] = 1 no such edge in E(G), adj_mat [ i ][j] = 0 symmetric for an undirected graph the degree of any vertex, i , for an undirected graph its row sum for a directed graph row sum is the out-degree disadvantages hard to find out the number of edges in a graph in the case of sparse graphs for more conveniences we must consider an adjacent list  

12. The Graph Abstract Data Type(Cont’d) Graph Representation(Cont’d) Adjacent Lists node structure the starting point of the list for vertex i node[ i ] the number of nodes in its adjacency list the degree of any vertex in an undirected graph the number of edges incident on the vertex the out-degree of any vertex in an directed graph inverse adjacency list the in-degree of a vertex all vertices adjacent to a vertex Class Node{ int vertex; Node link; }

13. The Graph Abstract Data Type(Cont’d) Graph Representation(Cont’d) Adjacent Lists(Cont’d) Changing node structure The problem of finding in-degree Class Node{ int tail; int head Node columnLinkForHead ; Node rowLinkForTail ; }

14. The Graph Abstract Data Type(Cont’d) Graph Representation(Cont’d) Adjacent Multilists

15. The Graph Abstract Data Type(Cont’d) Graph Representation(Cont’d) Weighted Edges weights may represent the distance or the cost network a graph with weighted edges

16. Elementary Graph Operations Depth First Search similar to a preorder tree traversal using a stack Process visit the start vertex v select an unvisited vertex, w, from v’s adjacency list v is placed on a stack reaches a vertex, u, that has no visited vertices on v’s adjacency list remove a vertex from the stack processing its adjacency list previously visited vertices are discarded unvisited vertices are visited and placed on the stack terminates the stack is empty void dfs ( int v){ visited[v] = true; System.out.println (v); for(Node w = graph[v] ; w != null ; w = w.link ){ if(!visited[ w.vertex ]) dfs ( w.vertex ); } } v v 1 v 3 v 7 v 4 v 5 v 2 v 6 time complexity adjacency list = O(e) adjacency matrix = O( n 2 )

17. Elementary Graph Operations(Cont’d) Breath First Search resembles a level order traversal using a queue Process visit the vertex v and marks it visit all of the first vertex on v’s adjacency list each vertex is placed to queue all of vertices on v’s adjacency list are visited remove a vertex from the queue examine the vertex again that is removed from the queue visited vertices are ignored the search is finished when the queue is empty

18. Elementary Graph Operations(Cont’d) Breath First Search(Cont’d) class Queue{ int vertex; Queue link; } void bfs ( int v){ Queue front = null, rear=null; System.out.println (v); visited[v] = true; addq (front, rear, v); while(front != null){ v = deleteq (front); for(Node w = graph[v] ; w != null ; w = w.link ){ if(!visited[ w.vertex ]){ System.out.println ( w.vertex ); addq (front, rear, w.vertex ); visited[w] = true; } } } } v v 1 v 2 v 3 v 4 v 5 v 6 v 7 Time complexity adjacency list = O(e) adjacency matrix = O( n 2 )

19. Elementary Graph Operations(Cont’d) Connected Component determining whether or not an undirected graph is connected calling either dfs (0) or bfs (0) it determined as an unconnected graph we can list up the connected components of a graph repeated calls to either dfs (v) or bfs (v) whee v is unvisited vertex void connected(){ for( int i = 0 ; i < n ; i ++){ if(!visited[ i ]){ dfs ( i ); System.out.println (); } } } Time complexity adjacency list = O( n+e ), ( dfs takes O(e), for loop takes O(n)) adjacency matrix = O( n 2 )

20. Elementary Graph Operations(Cont’d) Spanning Tree The search implicitly partitions the edges in G into two sets tree edges nontree edges tree edges set of traversed edges nontree edges set of remaining edges forming a tree if clause of either dfs or bfs it inserts the edge(v, w) a spanning tree is any tree consists solely of edges in G includes all the vertices in G a dfs and bfs spanning tree

21. Elementary Graph Operations(Cont’d) Spanning Tree(Cont’d) add a nontree edge(v, w) generating a cycle used for obtaining an independent set of circuit equations for an electrical network Ex) adding the nontree edge (7, 6)  7, 6, 2, 5, 7 minimal subgraph a spanning tree is a minimal subgraph of graph G any connected graph with n vertices must have at least n-1 edges all connected graph with n-1 edges are trees a spanning tree has n-1 edges assign weights to the edges the cost of constructing the communication links or the length of the links minimum cost spanning trees

22. Elementary Graph Operations(Cont’d) Biconnected Components and Articulation Points Articulation Point a vertex to produce two connected components the articulation points 1, 3, 4, and 7 on the right images Biconnected Graph a connected graph that has no articulation points loss of communication an articulation point fails results a loss of communication biconnected components having no more than one vertex in common

23. Elementary Graph Operations(Cont’d) Biconnected Components and Articulation Points(Cont’d) finding the biconnected components use any depth first spanning tree depth first number the sequence of visiting the vertices back edge a nontree edge (u, v) either u is an ancestor of v or v is an ancestor of u all nontree edges are back edges dfs redrawn

24. Elementary Graph Operations(Cont’d) Biconnected Components and Articulation Points(Cont’d) finding an articulation point the root of the spanning tree and has two or more children not the root and u has a child w such that low(w) ≥ dfn (u) low(u) = min{ dfn (u), min{low(w) | w is a child of u}, min{ dfn (w), (u, w) is a back edge} } void dfnlow ( int u, int v){ dfn [u] = low[u] = num ++; for( Node ptr = graph[u] ; ptr != null ; ptr = ptr.link ){ w = ptr.vertex ; if( dfn [w] < 0){ dfnlow (w, u); low[u] = min(low[w], low[u]); } else if(w != v){ low[u] = min(low[u], dfn [w]); } } }

25. Elementary Graph Operations(Cont’d) Biconnected Components and Articulation Points(Cont’d) an articulation point(Cont’d) low(3) = min{ dfn (3) = 0, min{low(4) = 0}, min{ dfn (1) = 3} } = 0 low(4) = min{ dfn (4) = 1, min{low(2) = 0} } = 0 low(2) = min{ dfn (2) = 2, min{low(1) = 0} } = 0 low(1) = min{ dfn (1) = 3, min{low(0) = 4}, min{ dfn (3) = 0} } = 0 low(0) = min{ dfn (0) = 4 } = 4 low(5) = min{ dfn (5) = 5, min{low(6) = 5}, min{ dfn (7) = 7} } = 5 low(6) = min{ dfn (6) = 6, min{low(7) = 5} } = 5 low(7) = min{ dfn (7) = 7, min{low(8) = 9}, min{ dfn (5) = 5} } = 5 low(8) = min{ dfn (8) = 9 } = 9 low(9) = min{ dfn (9) = 8 } = 8

26. Elementary Graph Operations(Cont’d) Biconnected Components and Articulation Points(Cont’d) biconnected components of a graph void bicon ( int u, int v){ dfn [u] = low[u] = num ++; for( Node ptr = graph[u] ; ptr != null ; ptr = ptr.link ){ int w = ptr.vertex ; if(v != w && dfn [w] < dfn [u]){ push(top, u, w); if( dfn [w] < 0){ bicon (w, u); low[u] = min(low[u], low[w]); if(low[w] >= dfn [u]){ System.out.println (“New biconnected component:”); int x, y; do{ pop(top, x, y); System.out.println (“<“ + x + “, “ + y + “>”); }while(!((x == u) && (y == w))); System.out.println (); } } else if(w != u) low[u] = min(low[u], dfn [w]); } } }

27. Elementary Graph Operations(Cont’d) Biconnected Components and Articulation Points(Cont’d) biconnected components of a graph(Cont’d) 1 2 3 4 5 6 7 8 9 1 2 3 4 1 4 1 5 3 2 3 6 7 5 7 6 9 8 5 7 7 bicon (3, -1)

28. Minimum Cost Spanning Trees the cost of a spanning tree the sum of the costs(weights) greedy method an optimal solution for a wide variety of programming problems based on either a least cost or a highest profit criterion the constraints specified by the problem constraints of MCST must use only edges within the graph must use exactly n-1 edges may not use edges that would produce a cycle

29. Minimum Cost Spanning Trees(Cont’d) Kruscal’s Algorithm Algorithm selecting the edges in nondecreasing order of their cost a selected edge does not make a cycle n-1 edges will be selected for inclusion in T forming a forest at each stage of algorithm a formal description of Kruscal’s algorithm T = {}; while( T contains less than n-1 edges && E is not empty){ choose a least cost edge (v, w) from E; delete (v, w) from E; if((v, w) does not create a cycle in T){ add (v, w) to T; } else { discard(v, w); } } if( T contains fewer than n-1 edges){ print(“No spanning tree”); }

30. Minimum Cost Spanning Trees(Cont’d) Kruscal’s Algorithm(Cont’d) a cycle problem using the union-find operations adding an edge (v, w) using the find operation to see if they are in the same set Example) {0}, {1, 2, 3}, {5}, {6} an edge (2, 3) make a cycle, while an edge (1, 5) does not. adding an edge (v, w)

31. Minimum Cost Spanning Trees(Cont’d) Prim’s Algorithm Algorithm beginning with a tree, T, that contains a single vertex adding an edge (u, v) to T ( T U {(u, v)} is also a tree ) repeating this edge addition until T contains n-1 edges forming a tree at each stage a cycle problem choosing the edge (u, v) such that one of u or v is in T a formal description Prim’s algorithm T = { }; /* T is the set of tree edges */ TV = { 0 }; /* TV is the set of tree vertices */ while( T contains fewer than n-1 edges ){ let (u, v) be a least cost edge such that u ∈ TV and v ∈ TV; if( there is no such edge){ break; add v to TV; add (u, v) to T; } if( T contains fewer than n-1 edges ){ print(“No spanning tree”); }

32. Minimum Cost Spanning Trees(Cont’d) Prim’s Algorithm(Cont’d) a strategy for this algorithm assuming a vertex v that is not in TV v has a companion vertex, near(v), such that near(v ) ∈ TV cost(near(v), v) is minimum faster implementations using Fibonacci heaps

33. Minimum Cost Spanning Trees(Cont’d) Sollin’s Algorithm Algorithm selecting several edges eliminating the duplicate edges selected edges and all vertices in a graph form a spanning forest selecting an edge from each tree that has the minimum cost in the forest adding a selected edge

34. Shortest Paths and Transitive Closure Shortest Paths Problems Single Source All Destination All Pairs Shortest Paths

35. Shortest Paths and Transitive Closure(Cont’d) Single Source All Destination Dijkstra’s Algorithm V V 1 50 V V 1 10 V 2 V 3 15 20 > if(distance[u] + cost[u][w] < distance[w ]){ distance[w ] = distance[u] + cost[u][w]; } int cost[][] = {{0, 50, 10, 1000, 45, 1000}, { 1000, 0, 15, 1000, 10, 1000}, { 20, 1000, 0, 15, 1000, 1000}, { 1000, 20, 1000, 0, 35, 1000}, { 1000, 1000, 30, 1000, 0, 1000}, { 1000, 1000, 1000, 3, 1000, 0} };

36. Shortest Paths and Transitive Closure(Cont’d) All Pairs Shortest Paths if( this.distanceAll [ i ][j] > this.distanceAll [ i ][k] + this.distanceAll [k][j]){ this.distanceAll [ i ][j] = this.distanceAll [ i ][k] + this.distanceAll [k][j]; } V V 2 11 V 4 V 1 V 2 2 >

37. Shortest Paths and Transitive Closure(Cont’d) Transitive Closure Transitive Closure A + [ i ][j] = 1 if there is a path of length > 0 from i to j Reflexive Transitive Closure A * [ i ][j] = 1 if there is a path of length ≥ 0 from i to j 1 2 3 4 if( this.distanceTrans [ i ][j] || this.distanceTrans [ i ][k] && this.distanceTrans [k][j]){ this.distanceTrans [ i ][j] = true; this.distanceReflexTrans [ i ][j] = this.distanceTrans [ i ][j]; }

38. Activity Networks AOV (Activity On Vertex) is a directed graph G vertices represent tasks or activities the edges represent precedence relations between activities predecessor vertex i is a predecessor of vertex j if there is a directed path from vertex i to vertex j immediate predecessor vertex i is an immediate predecessor of vertex j if < i , j> is an edge successor j is a successor of i if i is a predecessor of j immediate successor j is an immediate successor of i if i is an immediate predecessor of j

39. Activity Networks(Cont’d) AOV (Activity On Vertex)(Cont’d) feasible project the precedence relations must be both transitive and irreflexive transitive i∙j and j∙k  i∙k for all triples i , j, k irreflexive i∙i is false for all elements a directed acyclic graph a directed graph with no cycles a directed acyclic graph is proven that a precedence relation is irreflexive

40. Activity Networks(Cont’d) AOV (Activity On Vertex)(Cont’d) a topological order a linear ordering of the vertices of a graph Operations for( i = 0 ; i < n ; i ++){ if every vertex has a predecessor{ print(“Network has a cycle”); } pick a vertex v that has no predecessors; output v; delete v and all edges leading out of v from the network; } determine if a vertex has any predecessors (keeping a count of the number of immediate predecessors) b. delete a vertex and all of its incident edges (representing the network by adjacency lists)