Chapter 6 Graph s 337 3 4 17 LAX 1233 ORD 802 SFO 1843 DFW Outline and Reading Graphs 6 1 Definition Applications Terminology Properties ADT Data structures for graphs 6 2 Edge list structure Adjacency list structure Adjacency matrix structure To find the way out of a labyrinth there is only one means At every new junction never seen before the path we have taken will be marked with three signs If you see that the junction has already been visited you will make only one mark on the path you have taken If all the apertures have already been marked then you must retrace your steps But if one or two apertures of the junction are still without signs you will choose any one making two signs on it Proceeding through an aperture that bears only one sign you will make two more so that now the aperture bears three All the parts of the labyrinth must have been visited if arriving at a junction you never take a passage with three signs unless none of the other passages is now without signs Ancient Arabic text Graph Traversals How do you find your way out of a maze given a large supply of pennies Graph traversals Depth first search Breadth first search Other applications Boggle tic tac toe path finding theorem proving motion planning AI Graph A graph is a pair V E where V is a set of nodes called vertices E is a collection of pairs of vertices called edges Vertices and edges are positions and store elements Example A vertex represents an airport and stores the three letter airport code An edge represents a flight route between two airports and stores the mileage of the route SFO 337 HNL 2555 1843 43 7 1 LAX 1233 ORD 802 DFW 849 2 14 PVD LGA 87 3 1 1120 10 9 9 MIA Edge Types Directed edge Undirected edge unordered pair of vertices u v e g a flight route Directed graph ordered pair of vertices u v ORD first vertex u is the origin second vertex v is the destination e g a flight all the edges are directed e g route network Undirected graph all the edges are undirected e g flight network ORD flight AA 1206 PVD 849 miles PVD Applications Electronic circuits math brown edu cs brown edu Highway network Flight network brown edu Computer networks Local area network Internet Web qwest net att net Databases cslab1b Printed circuit board Integrated circuit Transportation networks cslab1a cox net Entity relationship diagram Paul John David Terminology End vertices or endpoints of an edge X has degree 5 Parallel edges U and V are adjacent Degree of a vertex a d and b are incident on V Adjacent vertices a Edges incident on a vertex U and V are the endpoints of a h and i are parallel edges Self loop j is a self loop U V b h X d c e W f Z i g Y j Terminology cont Path Simple path sequence of alternating vertices and edges begins with a vertex ends with a vertex each edge is preceded and followed by its endpoints path such that all its vertices and edges are distinct Examples P1 V b X h Z is a simple path P2 U c W e X g Y f W d V is a path that is not simple a U c V b d P2 P1 X e W g f Y h Z Terminology cont Cycle Simple cycle circular sequence of alternating vertices and edges each edge is preceded and followed by its endpoints cycle such that all its vertices and edges are distinct Examples C1 V b X g Y f W c U a is a simple cycle C2 U c W e X g Y f W d V a is a cycle that is not simple a U c V b d C2 X e C1 g W f h Y Z Properties Notation Property 1 v deg v 2m Proof each edge is counted twice Property 2 In an undirected graph with no self loops and no multiple edges m n n 1 2 Proof each vertex has degree at most n 1 What is the bound for a directed graph n m deg v number of vertices number of edges degree of vertex v Example n 4 m 6 deg v 3 Representing a Graph Two different drawings of the same graph are shown What data structure to represent this graph Adjacency Matrix A B C D A 1 1 0 B 0 0 C 0 D E F G H I J K L M E 0 0 0 1 F 1 0 0 1 1 G 1 0 0 0 1 0 H 0 0 0 0 0 0 0 I 0 0 0 0 0 0 0 1 J 0 0 0 0 0 0 0 0 0 K 0 0 0 0 0 0 0 0 0 1 L 0 0 0 0 0 0 0 0 0 1 0 M 0 0 0 Space required for a graph 0 with v vertices e edges 0 v2 0 0 Time to tell if there is an 0 edge from v1 to v2 0 1 1 0 1 Adjacency List A B C D E F G H I J K L M F A A E D D A I H K J M J B C G F F G E E L M J L Space required for a graph with v vertices e edges v e Time to tell if there is an edge from v1 to v2 v Main Methods of the Graph ADT Vertices and edges are positions store elements Accessor methods aVertex incidentEdges v endVertices e isDirected e origin e destination e opposite v e areAdjacent v w Update methods insertVertex o insertEdge v w o insertDirectedEdge v w o removeVertex v removeEdge e Generic methods numVertices numEdges vertices edges Asymptotic Performance n vertices m edges no parallel edges no self loops Bounds are big Oh Edge List Adjacency Matrix n m n2 incidentEdges v m n areAdjacent v w m 1 insertVertex o 1 n2 insertEdge v w o 1 1 removeVertex v m n2 removeEdge e 1 1 Space Depth First Search A B D C E Outline and Reading Definitions 6 1 Depth first search 6 3 1 Subgraph Connectivity Spanning trees and forests Algorithm Example Properties Analysis Applications of DFS 6 5 Path finding Cycle finding Subgraphs A subgraph S of a graph G is a graph such that The vertices of S are a subset of the vertices of G The edges of S are a subset of the edges of G Subgraph A spanning subgraph of G is a subgraph that contains all the vertices of G Spanning subgraph Connectivity A graph is connected if there is a path between every pair of vertices A connected component of a graph G is a maximal connected subgraph of G Connected graph Non connected graph with two connected Trees and Forests A free …
View Full Document
Unlocking...