Question? Leave a message!




UNDIRECTED GRAPHS

UNDIRECTED GRAPHS
ROBERT SEDGEWICK KEVIN WAYNE Algorithms 4.1 UNDIRECTED GRAPHS introduction ‣ graph API ‣ depthfirst search ‣ Algorithms FOUR TH EDITION breadthfirst search ‣ connected components ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.edu challenges ‣4.1 UNDIRECTED GRAPHS introduction ‣ graph API ‣ depthfirst search ‣ Algorithms breadthfirst search ‣ connected components ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.edu challenges ‣Undirected graphs Graph. Set of vertices connected pairwise by edges. Why study graph algorithms Thousands of practical applications. Hundreds of graph algorithms known. Interesting and broadly useful abstraction. Challenging branch of computer science and discrete math. 3Border graph of 48 contiguous United States 4Proteinprotein interaction network Reference: Jeong et al, Nature Review Genetics 5Map of science clickstreams http://www.plosone.org/article/info:doi/10.1371/journal.pone.0004803 610 million Facebook friends "Visualizing Friendships" by Paul Butler 8The evolution of FCC lobbying coalitions “The Evolution of FCC Lobbying Coalitions” by Pierre de Vries in JoSS Visualization Symposium 2010 9The Spread of Obesity in a Large Social Network Over 32 Years educational level; the ego’s obesity status at the ing both their weights. We estimated these mod previous time point (t); and most pertinent, the els in varied ego–alter pair types. 25 alter’s obesity status at times t and t + 1. We To evaluate the possibility that omitted vari used generalized estimating equations to account ables or unobserved events might explain the as for multiple observations of the same ego across sociations, we examined how the type or direc 26 examinations and across ego–alter pairs. We tion of the social relationship between the ego assumed an independent working correlation and the alter affected the association between the 26,27 structure for the clusters. ego’s obesity and the alter’s obesity. For example, The use of a timelagged dependent variable if unobserved factors drove the association be (lagged to the previous examination) eliminated tween the ego’s obesity and the alter’s obesity, serial correlation in the errors (evaluated with a then the directionality of friendship should not 28 Lagrange multiplier test ) and also substantial have been relevant. ly controlled for the ego’s genetic endowment and We evaluated the role of a possible spread in any intrinsic, stable predisposition to obesity. The smokingcessation behavior as a contributor to use of a lagged independent variable for an alter’s the spread of obesity by adding variables for the 25 weight status controlled for homophily. The smoking status of egos and alters at times t and key variable of interest was an alter’s obesity at t + 1 to the foregoing models. We also analyzed time t + 1. A significant coefficient for this vari the role of geographic distance between egos able would suggest either that an alter’s weight and alters by adding such a variable. Framingham heart study affected an ego’s weight or that an ego and an We calculated 95 confidence intervals by sim alter experienced contemporaneous events affect ulating the first difference in the alter’s contem Figure 1. Largest Connected Subcomponent of the Social Network in the Framingham Heart Study in the Year 2000. Each circle (node) represents one person in the data set. There are 2200 persons in this subcomponent of the social network. Circles with red borders denote women, and circles with blue borders denote men. The size of each circle is proportional to the person’s bodymass index. The interior color of the circles indicates the person’s obesity status: yellow denotes an obese person (bodymass index, ≥30) and green denotes a nonobese person. The colors of the ties between the nodes indicate the relationship between them: purple denotes a friendship or marital tie and orange denotes a familial tie. “The Spread of Obesity in a Large Social Network over 32 Years” by Christakis and Fowler in New England Journal of Medicine, 2007 10 373 n engl j med 357;4 www.nejm.org july 26, 2007The Internet as mapped by the Opte Project http://en.wikipedia.org/wiki/Internet 11Graph applications graph vertex edge telephone, computer fiber optic cable communication gate, register, processor wire circuit joint rod, beam, spring mechanical stock, currency transactions financial intersection street transportation class C network connection internet board position legal move game person friendship social relationship neuron synapse neural network protein proteinprotein interaction protein network atom bond molecule 12Graph terminology Path. Sequence of vertices connected by edges. Cycle. Path whose first and last vertices are the same. Two vertices are connected if there is a path between them. vertex edge cycle of length 5 path of length 4 vertex of degree 3 connected components Anatomy of a graph 13Some graphprocessing problems problem description st path Is there a path between s and t shortest st path What is the shortest path between s and t cycle Is there a cycle in the graph Euler cycle Is there a cycle that uses each edge exactly once Hamilton cycle Is there a cycle that uses each vertex exactly once connectivity Is there a way to connect all of the vertices biconnectivity Is there a vertex whose removal disconnects the graph planarity Can the graph be drawn in the plane with no crossing edges graph isomorphism Do two adjacency lists represent the same graph Challenge. Which graph problems are easy difficult intractable 144.1 UNDIRECTED GRAPHS introduction ‣ graph API ‣ depthfirst search ‣ Algorithms breadthfirst search ‣ connected components ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.edu challenges ‣Graph representation Graph drawing. Provides intuition about the structure of the graph. two drawings of the same graph Two drawings of the same graph Caveat. Intuition can be misleading. 16 Two drawings of the same graphGraph representation Vertex representation. This lecture: use integers between 0 and V – 1. Applications: convert between names and integers with symbol table. A 0 B C G 1 2 6 symbol table D E 3 4 F 5 parallel selfloop edges Anomalies. Anomalies 17Graph API public class public class Graph Graph Graph(int V) Graph(int V) create an empty graph with V vertices Graph(In in) Graph(In in) create a graph from input stream void addEdge(int v, int w) addEdge(int v, int w) add an edge vw IterableInteger adj(int v) adj(int v) vertices adjacent to v int V() V() number of vertices int E() E() number of edges In in = new In(args0); read graph from input stream Graph G = new Graph(in); for (int v = 0; v G.V(); v++) print out each for (int w : G.adj(v)) edge (twice) StdOut.println(v + "" + w); 18Graph API: sample client Graph input format. java Test tinyG.txt tinyG.txt mediumG.txt V V 06 13 250 E E 13 1273 02 0 5 244 246 01 4 3 239 240 05 0 1 238 245 10 9 12 235 238 6 4 233 240 20 5 4 232 248 35 0 2 231 248 34 229 249 11 12 ⋮ 228 241 9 10 226 231 0 6 1211 ... 7 8 129 (1261 additional lines) 9 11 5 3 Input format for Graph constructor (two examples) In in = new In(args0); read graph from input stream Graph G = new Graph(in); for (int v = 0; v G.V(); v++) print out each for (int w : G.adj(v)) edge (twice) StdOut.println(v + "" + w); 19Typical graphprocessing code public class public class Graph Graph Graph(int V) Graph(int V) create an empty graph with V vertices Graph(In in) Graph(In in) create a graph from input stream void addEdge(int v, int w) addEdge(int v, int w) add an edge vw IterableInteger adj(int v) adj(int v) vertices adjacent to v int V() V() number of vertices int E() E() number of edges // degree of vertex v in graph G public static int degree(Graph G, int v) int degree = 0; for (int w : G.adj(v)) degree++; return degree; 20Setofedges graph representation Maintain a list of the edges (linked list or array). 0 0 1 0 2 1 2 6 0 5 0 6 3 4 3 4 3 5 4 5 5 4 6 7 8 9 10 9 10 9 11 7 8 9 12 11 12 11 12 Q. How long to iterate over vertices adjacent to v 21Adjacencymatrix graph representation Maintain a twodimensional VbyV boolean array; for each edge v–w in graph: adjvw = adjwv = true. two entries for each edge 0 0 1 2 3 4 5 6 7 8 9 10 11 12 0 0 1 1 0 0 1 1 0 0 0 0 0 0 1 2 6 1 1 0 0 0 0 0 0 0 0 0 0 0 0 2 1 0 0 0 0 0 0 0 0 0 0 0 0 3 3 4 0 0 0 0 1 1 0 0 0 0 0 0 0 4 0 0 0 1 0 1 1 0 0 0 0 0 0 5 1 0 0 1 1 0 0 0 0 0 0 0 0 5 6 1 0 0 0 1 0 0 0 0 0 0 0 0 7 0 0 0 0 0 0 0 0 1 0 0 0 0 9 10 8 0 0 0 0 0 0 0 1 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 1 1 1 7 8 10 0 0 0 0 0 0 0 0 0 1 0 0 0 11 0 0 0 0 0 0 0 0 0 1 0 0 1 11 12 12 0 0 0 0 0 0 0 0 0 1 0 1 0 Q. How long to iterate over vertices adjacent to v 22Adjacencylist graph representation Maintain vertexindexed array of lists. 6 2 1 5 0 Bag objects 0 0 adj 5 4 0 1 2 6 1 5 6 3 2 3 3 4 0 4 3 4 5 0 4 6 5 7 8 8 representations 9 of the same edge 9 10 7 10 11 11 10 12 7 8 12 11 12 9 9 12 11 9 Q. How long to iterate over vertices adjacent to v 23 Adjacencylists representation (undirected graph)Graph representations In practice. Use adjacencylists representation. Algorithms based on iterating over vertices adjacent to v. Realworld graphs tend to be sparse. huge number of vertices, small average vertex degree sparse (E = 200) dense (E = 1000) Two graphs (V = 50) 24Graph representations In practice. Use adjacencylists representation. Algorithms based on iterating over vertices adjacent to v. Realworld graphs tend to be sparse. huge number of vertices, small average vertex degree edge between iterate over vertices representation space add edge v and w adjacent to v list of edges E 1 E E 2 adjacency matrix V 1 1 V adjacency lists E + V 1 degree(v) degree(v) disallows parallel edges 25Adjacencylist graph representation: Java implementation public class Graph private final int V; adjacency lists private BagInteger adj; ( using Bag data type ) public Graph(int V) this.V = V; create empty graph adj = (BagInteger) new BagV; with V vertices for (int v = 0; v V; v++) adjv = new BagInteger(); public void addEdge(int v, int w) add edge vw (parallel edges and adjv.add(w); selfloops allowed) adjw.add(v); iterator for vertices adjacent to v public IterableInteger adj(int v) return adjv; 264.1 UNDIRECTED GRAPHS introduction ‣ graph API ‣ depthfirst search ‣ Algorithms breadthfirst search ‣ connected components ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.edu challenges ‣Maze exploration Maze graph. Vertex = intersection. Edge = passage. intersection passage Goal. Explore every intersection in the maze. 28Trémaux maze exploration Algorithm. Unroll a ball of string behind you. Mark each visited intersection and each visited passage. Retrace steps when no unvisited options. Tremaux exploration 29Trémaux maze exploration Algorithm. Unroll a ball of string behind you. Mark each visited intersection and each visited passage. Retrace steps when no unvisited options. First use Theseus entered Labyrinth to kill the monstrous Minotaur; Ariadne instructed Theseus to use a ball of string to find his way back out. The Labyrinth (with Minotaur) Claude Shannon (with Theseus mouse) 30Maze exploration: easy 31Maze exploration: medium 32Maze exploration: challenge for the bored 33Depthfirst search Goal. Systematically traverse a graph. functioncall stack acts as ball of string Idea. Mimic maze exploration. DFS (to visit a vertex v) Mark v as visited. Recursively visit all unmarked vertices w adjacent to v. Typical applications. Find all vertices connected to a given source vertex. Find a path between two vertices. Design challenge. How to implementDepthfirst search demo To visit a vertex v : Mark vertex v as visited. Recursively visit all unmarked vertices adjacent to v. mediumG.txt tinyG.txt 0 0 0 7 7 8 8 7 8 V V 13 250 E E 13 1273 0 5 244 246 4 3 239 240 0 1 238 245 1 1 1 2 2 2 6 6 6 9 9 10 10 9 10 9 12 235 238 6 4 233 240 5 4 232 248 0 2 231 248 11 12 229 249 3 3 3 4 4 4 11 11 12 12 11 12 9 10 228 241 0 6 226 231 7 8 ... 9 11 (1261 additional lines) 5 5 5 5 3 Input format for Graph constructor (two examples) graph G 35Depthfirst search demo To visit a vertex v : Mark vertex v as visited. Recursively visit all unmarked vertices adjacent to v. v marked edgeTo 0 7 8 7 8 0 T – 1 T 0 2 T 0 3 T 5 1 2 6 9 10 9 10 4 T 6 5 T 4 6 T 0 3 4 11 12 11 12 7 F – 8 F – 9 F – 10 F – 5 11 F – 12 F – vertices reachable from 0 36Design pattern for graph processing Design pattern. Decouple graph data type from graph processing. Create a Graph object. Pass the Graph to a graphprocessing routine. Query the graphprocessing routine for information. public class public class Paths Paths Paths(Graph G, int s) Paths(Graph G, int s) find paths in G from source s boolean hasPathTo(int v) hasPathTo(int v) is there a path from s to v IterableInteger pathTo(int v) pathTo(int v) path from s to v; null if no such path Paths paths = new Paths(G, s); for (int v = 0; v G.V(); v++) if (paths.hasPathTo(v)) print all vertices StdOut.println(v); connected to s 37Depthfirst search: data structures To visit a vertex v : Mark vertex v as visited. Recursively visit all unmarked vertices adjacent to v. Data structures. Boolean array marked to mark visited vertices. Integer array edgeTo to keep track of paths. (edgeTow == v) means that edge vw taken to visit w for first time Functioncall stack for recursion. Depthfirst search: Java implementation public class DepthFirstPaths markedv = true private boolean marked; if v connected to s private int edgeTo; edgeTov = previous private int s; vertex on path from s to v public DepthFirstPaths(Graph G, int s) initialize data structures ... dfs(G, s); find vertices connected to s private void dfs(Graph G, int v) recursive DFS does the work markedv = true; for (int w : G.adj(v)) if (markedw) dfs(G, w); edgeTow = v; 39Depthfirst search: properties Proposition. DFS marks all vertices connected to s in time proportional to the sum of their degrees (plus time to initialize the marked array). set of marked Pf. correctness source vertices If w marked, then w connected to s (why) s If w connected to s, then w marked. (if w unmarked, then consider last edge on a path from s to w that goes from a v no such edge set of can exist marked vertex to an unmarked one). unmarked vertices x Pf. running time Each vertex connected to s is visited once. w 40Depthfirst search: properties Proposition. After DFS, can check if vertex v is connected to s in constant time and can find v–s path (if one exists) in time proportional to its length. Pf. edgeTo is parentlink representation of a tree rooted at vertex s. public boolean hasPathTo(int v) return markedv; edgeTo public IterableInteger pathTo(int v) 0 1 2 if (hasPathTo(v)) return null; 2 0 StackInteger path = new StackInteger(); 3 2 for (int x = v; x = s; x = edgeTox) 4 3 path.push(x); 5 3 path.push(s); x path return path; 5 5 3 3 5 2 2 3 5 0 0 2 3 5 Trace of pathTo() computation 41Depthfirst search application: flood fill Challenge. Flood fill (Photoshop magic wand). Assumptions. Picture has millions to billions of pixels. Solution. Build a grid graph (implicitly). Vertex: pixel. Edge: between two adjacent gray pixels. Blob: all pixels connected to given pixel. 42Depthfirst search application: preparing for a date http://xkcd.com/761/ 434.1 UNDIRECTED GRAPHS introduction ‣ graph API ‣ depthfirst search ‣ Algorithms breadthfirst search ‣ connected components ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.edu challenges ‣Breadthfirst search demo Repeat until queue is empty: Remove vertex v from queue. Add to queue all unmarked vertices adjacent to v and mark them. tinyCG.txt standard drawing 0 0 2 2 V 6 E 8 0 5 2 4 1 1 2 3 1 2 drawing with both edges 0 1 3 4 3 3 3 5 5 5 4 4 0 2 adjacency lists 2 1 5 graph G 0 2 adj 45 0 0 1 3 4 1 2 5 4 2 3 4 3 2 5 3 0 A connected undirected graphBreadthfirst search demo Repeat until queue is empty: Remove vertex v from queue. Add to queue all unmarked vertices adjacent to v and mark them. 0 2 v edgeTo distTo 0 – 0 1 0 1 1 2 0 1 3 2 2 4 2 2 3 5 0 1 5 4 done 46Breadthfirst search Repeat until queue is empty: Remove vertex v from queue. Add to queue all unmarked vertices adjacent to v and mark them. BFS (from source vertex s) Put s onto a FIFO queue, and mark s as visited. Repeat until the queue is empty: remove the least recently added vertex v add each of v's unvisited neighbors to the queue, and mark them as visited. Breadthfi rst maze exploration 47Breadthfirst search: Java implementation public class BreadthFirstPaths private boolean marked; private int edgeTo; private int distTo; … private void bfs(Graph G, int s) QueueInteger q = new QueueInteger(); initialize FIFO queue of q.enqueue(s); vertices to explore markeds = true; distTos = 0; while (q.isEmpty()) int v = q.dequeue(); for (int w : G.adj(v)) if (markedw) q.enqueue(w); found new vertex w markedw = true; via edge vw edgeTow = v; distTow = distTov + 1; 48Breadthfirst search properties Q. In which order does BFS examine vertices A. Increasing distance (number of edges) from s. queue always consists of ≥ 0 vertices of distance k from s, followed by ≥ 0 vertices of distance k+1 Proposition. In any connected graph G, BFS computes shortest paths from s to all other vertices in time proportional to E + V. 1 4 s 0 2 1 0 2 3 3 5 4 5 graph G dist = 0 dist = 1 dist = 2 49Breadthfirst search application: routing Fewest number of hops in a communication network. ARPANET, July 1977 50Breadthfirst search application: Kevin Bacon numbers Endless Games board game SixDegrees iPhone App http://oracleofbacon.org 51Kevin Bacon graph Include one vertex for each performer and one for each movie. Connect a movie to all performers that appear in that movie. Compute shortest path from s = Kevin Bacon. Grace Patrick Dial M Caligola Kelly Allen for Murder Glenn The Stepford Close High Wives To Catch Noon a Thief John Gielgud Portrait Lloyd The Eagle of a Lady Bridges Nicole Has Landed Kidman Murder on the Orient Express Donald Cold Kathleen Joe Versus Sutherland Mountain Quinlan the Volcano An American John Animal Hamlet performer Haunting Belushi House Apollo 13 vertex Vernon Dobtcheff The Kevin Woodsman Bacon Tom Hanks Bill movie Paxton Wild vertex Things The River Jude Wild The Da Paul Vinci Code Herbert Meryl Streep Serretta Enigma Wilson Kate Winslet Yves Titanic Aubert Shane Eternal Sunshine Zaza of the Spotless Mind 52 V and E not explicitly movies.txt specified ... Tin Men (1987)/DeBoy, David/Blumenfeld, Alan/... /Geppi, Cindy/Hershey, Barbara... Tirez sur le pianiste (1960)/Heymann, Claude/.../Berger, Nicole (I)... Titanic (1997)/Mazin, Stan/...DiCaprio, Leonardo/.../Winslet, Kate/... Titus (1999)/Weisskopf, Hermann/Rhys, Matthew/.../McEwan, Geraldine To Be or Not to Be (1942)/Verebes, Ernö (I)/.../Lombard, Carole (I)... To Be or Not to Be (1983)/.../Brooks, Mel (I)/.../Bancroft, Anne/... To Catch a Thief (1955)/París, Manuel/.../Grant, Cary/.../Kelly, Grace/... To Die For (1995)/Smith, Kurtwood/.../Kidman, Nicole/.../ Tucci, Maria... ... "/" delimiter Symbol graph example (adjacency lists)Breadthfirst search application: Erdös numbers handdrawing of part of the Erdös graph by Ron Graham 534.1 UNDIRECTED GRAPHS introduction ‣ graph API ‣ depthfirst search ‣ Algorithms breadthfirst search ‣ connected components ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.edu challenges ‣Connectivity queries Def. Vertices v and w are connected if there is a path between them. Goal. Preprocess graph to answer queries of the form is v connected to w in constant time. public class public class CC CC CC(Graph G) CC(Graph G) find connected components in G boolean connected(int v, int w) connected(int v, int w) are v and w connected int count() count() number of connected components component identifier for v int id(int v) id(int v) (between 0 and count() 1) UnionFind Not quite. Depthfirst search. Yes. next few slides 55Connected components The relation "is connected to" is an equivalence relation: Reflexive: v is connected to v. Symmetric: if v is connected to w, then w is connected to v. Transitive: if v connected to w and w connected to x, then v connected to x. Def. A connected component is a maximal set of connected vertices. v id 0 0 7 8 0 1 0 2 0 3 0 1 2 6 4 0 9 10 5 0 6 0 3 4 7 1 8 1 11 12 5 9 2 10 2 11 2 3 connected components 12 2 Remark. Given connected components, can answer queries in constant time. 56Connected components Def. A connected component is a maximal set of connected vertices. 63 connected components 57Connected components Goal. Partition vertices into connected components. Connected components Initialize all vertices v as unmarked. For each unmarked vertex v, run DFS to identify all tinyG.txt mediumG.txt V V vertices discovered as part of the same component. 13 250 E E 1273 13 244 246 0 5 mediumG.txt tinyG.txt 4 3 239 240 V V 250 13 0 1 238 245 E E 235 238 9 12 13 1273 233 240 6 4 0 5 244 246 5 4 232 248 239 240 4 3 0 2 231 248 0 1 238 245 229 249 11 12 9 12 235 238 228 241 9 10 233 240 6 4 0 6 226 231 232 248 5 4 7 8 ... 0 2 231 248 (1261 additional lines) 9 11 229 249 11 12 5 3 228 241 9 10 Input format for Graph constructor (two examples) 0 6 226 231 58 ... 7 8 (1261 additional lines) 9 11 5 3 Input format for Graph constructor (two examples)Connected components demo To visit a vertex v : Mark vertex v as visited. Recursively visit all unmarked vertices adjacent to v. v marked id 0 0 0 7 7 8 8 7 8 0 F – 1 F – 2 F – 3 F – 1 1 1 2 2 2 6 6 6 9 9 10 10 9 10 4 F – 5 F – 6 F – 3 3 3 4 4 4 11 11 12 12 11 12 7 F – 8 F – 9 F – 5 5 10 F – 5 11 F – 12 F – graph G 59Connected components demo To visit a vertex v : Mark vertex v as visited. Recursively visit all unmarked vertices adjacent to v. v marked id 0 7 8 0 T 0 1 T 0 2 T 0 3 T 0 1 2 6 9 10 4 T 0 5 T 0 6 T 0 3 4 11 12 7 T 1 8 T 1 9 T 2 10 T 2 5 11 T 2 12 T 2 done 60Finding connected components with DFS public class CC private boolean marked; idv = id of component containing v private int id; number of components private int count; public CC(Graph G) marked = new booleanG.V(); id = new intG.V(); for (int v = 0; v G.V(); v++) if (markedv) run DFS from one vertex in dfs(G, v); each component count++; public int count() see next slide public int id(int v) public boolean connected(int v, int w) private void dfs(Graph G, int v) 61Finding connected components with DFS (continued) public int count() number of components return count; public int id(int v) id of component containing v return idv; public boolean connected(int v, int w) v and w connected iff same id return idv == idw; private void dfs(Graph G, int v) markedv = true; all vertices discovered in idv = count; same call of dfs have same id for (int w : G.adj(v)) if (markedw) dfs(G, w); 62Connected components application: study spread of STDs Relationship graph at "Jefferson High" Peter Bearman, James Moody, and Katherine Stovel. Chains of affection: The structure of adolescent romantic and sexual networks. American Journal of Sociology, 110(1): 44–99, 2004. 63Connected components application: particle detection Particle detection. Given grayscale image of particles, identify "blobs." Vertex: pixel. Edge: between two adjacent pixels with grayscale value ≥ 70. Blob: connected component of 2030 pixels. black = 0 white = 255 Particle tracking. Track moving particles over time. 644.1 UNDIRECTED GRAPHS introduction ‣ graph API ‣ depthfirst search ‣ Algorithms breadthfirst search ‣ connected components ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.edu challenges ‣Graphprocessing challenge 1 Problem. Is a graph bipartite 0 01 02 05 1 2 6 06 13 How difficult 3 4 23 24 Any programmer could do it. 5 45 ✓ Typical diligent algorithms student could do it. 46 Hire an expert. simple DFSbased solution Intractable. 0 01 (see textbook) No one knows. 02 05 1 2 6 Impossible. 06 13 3 4 23 24 5 45 46 0, 3, 4 66Bipartiteness application: is dating graph bipartite Image created by Mark Newman. 67Graphprocessing challenge 2 Problem. Find a cycle. 0 01 02 05 1 2 6 06 13 How difficult 3 4 23 24 Any programmer could do it. 5 45 ✓ Typical diligent algorithms student could do it. 46 05460 Hire an expert. simple DFSbased solution Intractable. (see textbook) No one knows. Impossible. 68Bridges of Königsberg The Seven Bridges of Königsberg. Leonhard Euler 1736 “ … in Königsberg in Prussia, there is an island A, called the Kneiphof; the river which surrounds it is divided into two branches ... and these branches are crossed by seven bridges. Concerning these bridges, it was asked whether anyone could arrange a route in such a way that he could cross each bridge once and only once. ” Euler cycle. Is there a (general) cycle that uses each edge exactly once Answer. A connected graph is Eulerian iff all vertices have even degree. 69Graphprocessing challenge 3 Problem. Find a (general) cycle that uses every edge exactly once. 0 01 02 05 1 2 6 06 12 How difficult 3 4 23 24 Any programmer could do it. 5 34 ✓ Typical diligent algorithms student could do it. 45 46 Hire an expert. 01234206450 Euler cycle Intractable. (classic graphprocessing problem) No one knows. Impossible. 70Graphprocessing challenge 4 Problem. Find a cycle that visits every vertex exactly once. 0 01 02 05 1 2 6 06 12 How difficult 3 4 26 34 Any programmer could do it. 5 35 Typical diligent algorithms student could do it. 45 46 Hire an expert. 05346210 ✓ Intractable. Hamilton cycle No one knows. (classical NPcomplete problem) Impossible. 71Graphprocessing challenge 5 Problem. Are two graphs identical except for vertex names 0 01 02 05 1 2 6 06 34 How difficult 3 4 35 45 Any programmer could do it. 5 46 Typical diligent algorithms student could do it. Hire an expert. Intractable. 04 3 05 ✓ No one knows. 2 06 4 Impossible. 14 1 graph isomorphism is 15 6 longstanding open problem 24 5 34 56 0 0↔4, 1↔3, 2↔2, 3↔6, 4↔5, 5↔0, 6↔1 72Graphprocessing challenge 6 Problem. Lay out a graph in the plane without crossing edges 01 1 02 2 05 0 06 6 34 3 How difficult 35 4 45 Any programmer could do it. 46 5 Typical diligent algorithms student could do it. Hire an expert. ✓ Intractable. 0 lineartime DFSbased planarity algorithm No one knows. discovered by Tarjan in 1970s (too complicated for most practitioners) 1 2 6 Impossible. 3 4 5 73Graph traversal summary BFS and DFS enables efficient solution of many (but not all) graph problems. problem BFS DFS time ✔ ✔ path between s and t E + V ✔ shortest path between s and t E + V ✔ ✔ connected components E + V ✔ biconnected components E + V ✔ ✔ cycle E + V ✔ Euler cycle E + V 1.657V Hamilton cycle 2 ✔ ✔ bipartiteness E + V ✔ planarity E + V c V logV graph isomorphism 2 74
sharer
Presentations
Free
Document Information
Category:
Presentations
User Name:
Dr.BenjaminClark
User Type:
Teacher
Country:
United States
Uploaded Date:
21-07-2017