Graphs 337 LAX 2010 Goodrich Tamassia Graphs 3 4 17 1233 ORD 802 SFO 1843 DFW 1 Graphs 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 2010 Goodrich Tamassia 337 HNL 2555 LAX 1843 43 7 1 1233 ORD 802 DFW Graphs 849 2 14 PVD LGA 87 3 1 1120 10 9 9 MIA 2 Edge Types Directed edge Undirected edge unordered pair of vertices u v e g a flight route flight ORD AA 1206 PVD ORD 849 miles PVD Directed graph ordered pair of vertices u v 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 2010 Goodrich Tamassia Graphs 3 Applications cslab1a Electronic circuits Printed circuit board Integrated circuit cs brown edu Highway network Flight network brown edu qwest net Computer networks math brown edu Transportation networks cslab1b Local area network Internet Web Databases att net cox net John Paul Entity relationship diagram 2010 Goodrich Tamassia Graphs David 4 Terminology End vertices or endpoints of an edge b d X has degree 5 e j Z i g f h and i are parallel edges h X W Self loop V c U and V are adjacent Parallel edges U 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 Y j is a self loop 2010 Goodrich Tamassia Graphs 5 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 Importance of distinction 2010 Goodrich Tamassia Graphs a U c V b d P2 P1 X e W h Z g f Y 6 Terminology cont Cycle circular sequence of alternating vertices and edges each edge is preceded and followed by its endpoints First and last vertex is same a U c V b d C2 X e 2010 Goodrich Tamassia Graphs C1 g W f h Z Y 7 Terminology cont Simple cycle cycle such that all its vertices and edges are distinct a cycle in an undirected graph may not have repeated edges why What about directed graph 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 2010 Goodrich Tamassia Graphs a U c V b d C2 X e C1 g W f h Z Y 8 Terminology cont The length of a path or a cycle is its number of edges We say that one vertex is connected to another if there exists a path that contains both of them A graph is connected if there is a path from every vertex to every other vertex An acyclic graph is a graph with no cycles Example of a graph that is acyclic 2010 Goodrich Tamassia Graphs a U c V b d C2 X e C1 g W f h Z Y 9 Terminology cont A tree is an acyclic connected graph A forest is a disjoint set of trees a U c V b d C2 X e 2010 Goodrich Tamassia Graphs C1 g W f h Z Y 10 Digraphs A digraph is a graph whose edges are all directed E D Short for directed graph C Applications B one way streets flights task scheduling 2010 Goodrich Tamassia Directed Graphs A 11 Graph Connectivity An undirected graph is said to be connected if there is a path between every pair of nodes Otherwise the graph is disconnected Informally an undirected graph is connected if it hangs in one piece Connected Disconnected CS 103 12 Connectivity Q Which of the following graphs are connected 1 2 3 L24 4 13 Connectivity A First and second are disconnected Last is connected 1 2 3 L24 4 14 Connectivity 2010 Goodrich Tamassia Graphs 15 Connectivity in Directed Graphs I Definition A directed graph is said to be strongly connected if for any pair of nodes there is a path from each one to the other A B C D E 16 Connectivity in Directed Graphs II Definition A directed graph is said to be weakly connected if the underlying undirected graph is connected A Each unilaterally connected graph is also weakly connected B C D E There is no path between B and D 17 Directed Graphs Are these two graphs same 2010 Goodrich Tamassia Graphs 18 Properties Notation Property 1 v deg v 2m n m deg v Proof each edge is counted twice number of vertices number of edges degree of vertex v 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 Example n 4 m 6 deg v 3 What is the bound for a directed graph 2010 Goodrich Tamassia Graphs 19 E Digraph Properties D C B A graph G V E such that Each edge goes in one direction A Edge a b goes from a to b but not b to a If G is simple m n n 1 If we keep in edges and out edges in separate adjacency lists we can perform listing of incoming edges and outgoing edges in time proportional to their size 2010 Goodrich Tamassia Directed Graphs 20 Main Methods of the Graph ADT Vertices and edges Update methods are positions store elements Accessor methods e endVertices a list of the two endvertices of e e opposite v the vertex opposite of v on e u isAdjacentTo v true iff u and v are adjacent v reference to element associated with vertex v e reference to element associated with edge e 2010 Goodrich Tamassia Graphs insertVertex o insert a vertex storing element o insertEdge v w o insert an edge v w storing element o eraseVertex v remove vertex v and its incident edges eraseEdge e remove edge e Iterable collection methods incidentEdges v list of edges incident to v vertices list of all vertices in the graph edges list of all edges in the graph 21 Graph Representation For graphs to be computationally useful they have to be conveniently represented in programs There are two computer representations of graphs Adjacency matrix representation Adjacency lists representation CS 103 22 Adjacency Matrix Representation In this representation each graph of n nodes is represented by an n …