算法设计与分析算法设计与分析 (4).ppt
1Chapter 3GraphsSlides by Kevin Wayne.Copyright 2005 Pearson-Addison Wesley.All rights reserved.3.1 Basic Definitions and Applications3Undirected GraphsUndirected graph.G=(V,E)nV=nodes.nE=edges between pairs of nodes.nCaptures pairwise relationship between objects.nGraph size parameters:n=|V|,m=|E|.V=1,2,3,4,5,6,7,8 E=1-2,1-3,2-3,2-4,2-5,3-5,3-7,3-8,4-5,5-6 n=8m=114Some Graph ApplicationstransportationGraphstreet intersectionsNodesEdgeshighwayscommunicationcomputersfiber optic cablesWorld Wide Webweb pageshyperlinkssocialpeoplerelationshipsfood webspeciespredator-preysoftware systemsfunctionsfunction callsschedulingtasksprecedence constraintscircuitsgateswires5Graph Representation:Adjacency MatrixAdjacency matrix.n-by-n matrix with Auv=1 if(u,v)is an edge.nTwo representations of each edge.nSpace proportional to n2.nChecking if(u,v)is an edge takes(1)time.nIdentifying all edges takes(n2)time.1 2 3 4 5 6 7 81 0 1 1 0 0 0 0 02 1 0 1 1 1 0 0 03 1 1 0 0 1 0 1 14 0 1 0 1 1 0 0 05 0 1 1 1 0 1 0 06 0 0 0 0 1 0 0 07 0 0 1 0 0 0 0 18 0 0 1 0 0 0 1 06Graph Representation:Adjacency ListAdjacency list.Node indexed array of lists.nTwo representations of each edge.nSpace proportional to m+n.nChecking if(u,v)is an edge takes O(deg(u)time.nIdentifying all edges takes(m+n)time.1232342556738813451258723465degree=number of neighbors of u377Paths and ConnectivityDef.A path in an undirected graph G=(V,E)is a sequence P of nodes v1,v2,vk-1,vk with the property that each consecutive pair vi,vi+1 is joined by an edge in E.Def.A path is simple if all nodes are distinct.Def.An undirected graph is connected if for every pair of nodes u and v,there is a path between u and v.8CyclesDef.A cycle is a path v1,v2,vk-1,vk in which v1=vk,k 2,and the first k-1 nodes are all distinct.cycle C=1-2-4-5-3-19TreesDef.An undirected graph is a tree if it is connected and does not contain a cycle.Theorem.Let G be an undirected graph on n nodes.Any two of the following statements imply the third.nG is connected.nG does not contain a cycle.nG has n-1 edges.10Rooted TreesRooted tree.Given a tree T,choose a root node r and orient each edge away from r.a treethe same tree,rooted at 1vparent of vchild of vroot r3.2 Graph Traversals-t connectivity problem.Given two node s and t,is there a path between s and t?s-t shortest path problem.Given two node s and t,what is the length of the shortest path between s and t?12Connectivity13Breadth First SearchExplore outward from s in all possible directions,adding nodes one layer at a time.BFS algorithm.nL0=s.nL1=all neighbors of L0.nL2=all nodes that do not belong to L0 or L1,and that have an edge to a node in L1.nLi+1=all nodes that do not belong to an earlier layer,and that have an edge to a node in Li.Theorem.For each i,Li consists of all nodes at distance exactly ifrom s.There is a path from s to t iff t appears in some layer.sL1L2L n-114Breadth First SearchProperty.Let T be a BFS tree of G=(V,E),and let(x,y)be an edge of G.Then the level of x and y differ by at most 1.L0L1L2L315Breadth First Search:AnalysisTheorem.The above implementation of BFS runs in O(m+n)time if the graph is given by its adjacency list representation.Pf.when we consider node u,there are deg(u)incident edges(u,v)total time processing edges is uV deg(u)=2m each edge(u,v)is counted exactly twicein sum:once in deg(u)and once in deg(v)16Connected ComponentConnected component.Find all nodes reachable from s.Connected component containing node 1=1,2,3,4,5,6,7,8.3.4 Testing Bipartiteness18Bipartite GraphsDef.An undirected graph G=(V,E)is bipartite if the nodes can be colored red or blue such that every edge has one red and one blue end.Applications.nStable marriage:men=red,women=blue.nScheduling:machines=red,jobs=blue.a bipartite graph19Testing BipartitenessTesting bipartiteness.Given a graph G,is it bipartite?nMany graph problems become:easier if the underlying graph is bipartite(matching)tractable if the underlying graph is bipartite(independent set)v1v2v3v6v5v4v7v2v4v5v7v1v3v6a bipartite graph Ganother drawing of G20An Obstruction to BipartitenessLemma.If a graph G is bipartite,it cannot contain an odd length cycle.Pf.Not possible to 2-color the odd cycle.bipartite(2-colorable)not bipartite(not 2-colorable)21Bipartite GraphsLemma.Let G be a connected graph,and let L0,Lk be the layers produced by BFS starting at node s.Exactly one of the following holds.(i)No edge of G joins two nodes of the same layer,and G is bipartite.(ii)An edge of G joins two nodes of the same layer,and G contains an odd-length cycle(and hence is not bipartite).Case(i)L1L2L3Case(ii)L1L2L322Obstruction to BipartitenessCorollary.A graph G is bipartite iff it contain no odd length cycle.5-cycle Cbipartite(2-colorable)not bipartite(not 2-colorable)3.5 Connectivity in Directed Graphs24Directed GraphsDirected graph.G=(V,E)nEdge(u,v)goes from node u to node v.Ex.Web graph-hyperlink points from one web page to another.nDirectedness of graph is crucial.nModern web search engines exploit hyperlink structure to rank web pages by importance.25Graph SearchDirected reachability.Given a node s,find all nodes reachable from s.Directed s-t shortest path problem.Given two node s and t,what is the length of the shortest path between s and t?Graph search.BFS extends naturally to directed graphs.Web crawler.Start from web page s.Find all web pages linked from s,either directly or indirectly.26Strong ConnectivityDef.Node u and v are mutually reachable if there is a path from u to v and also a path from v to u.Def.A graph is strongly connected if every pair of nodes is mutually reachable.Lemma.Let s be any node.G is strongly connected iff every node is reachable from s,and s is reachable from every node.svu27Strong Connectivity:AlgorithmTheorem.Can determine if G is strongly connected in O(m+n)time.Pf.nPick any node s.nRun BFS from s in G.nRun BFS from s in Grev.nReturn true iff all nodes reached in both BFS executions.nCorrectness follows immediately from previous lemma.reverse orientation of every edge in Gstrongly connectednot strongly connected3.6 DAGs and Topological Ordering29Directed Acyclic GraphsDef.An DAG is a directed graph that contains no directed cycles.Ex.Precedence constraints:edge(vi,vj)means vi must precede vj.Def.A topological order of a directed graph G=(V,E)is an ordering of its nodes as v1,v2,vn so that for every edge(vi,vj)we have i j.a DAGa topological orderingv2v3v6v5v4v7v1v1v2v3v4v5v6v730Directed Acyclic GraphsLemma.If G has a topological order,then G is a DAG.Pf.(by contradiction)nSuppose that G has a topological order v1,vn and that G also has a directed cycle C.Lets see what happens.nLet vi be the lowest-indexed node in C,and let vj be the node just before vi in C;thus(vj,vi)is an edge.nBy our choice of i,we have i j.nOn the other hand,since(vj,vi)is an edge and v1,vn is a topological order,we must have j 1 nodes,find a node v with no incoming edges.nG-v is a DAG,since deleting v cannot create cycles.nBy inductive hypothesis,G-v has a topological ordering.nPlace v first in topological ordering;then append nodes of G-v nin topological order.This is valid since v has no incoming edges.DAGv33Topological Sorting Algorithm:Running TimeTheorem.Algorithm finds a topological order in O(m+n)time.Pf.nMaintain the following information:countw=remaining number of incoming edgesS=set of remaining nodes with no incoming edgesnInitialization:O(m+n)via single scan through graph.nUpdate:to delete vremove v from Sdecrement countw for all edges from v to w,and add w to S if countw hits 0this is O(1)per edge.HomeworkRead Chapter 3 of the textbook.Exercises 2,5,6&8 in Chapter 3.34
