GraphsGraphThe Graph ADTDefinition : graphDefinition: digraphDefinition: order, sizeExampleDefinition: walk, length, path, cycleExample walksExample pathsExample cyclesDefinition: connected, strongly connectedConnected?Definition: degreeDegree, degree sequenceSlide 16Definition: diameterDiameterComputer representationsAdjacency matrices for G1,G2Adjacency lists for G1,G2Matrix vs. list representationGraphsCSCI 2720Spring 2005GraphWhy study graphs?important for many real-world applicationscompilers Communication networksReaction networks& moreThe Graph ADT a set of nodes (vertices or points) connection relations (edges or arcs) between those nodesDefinitions follow ….Definition : graphA graph G=(V,E) is a finite nonempty set V of objects called vertices (the singular is vertex) together with a (possibly empty) set E of unordered pairs of distinct vertices of G called edges. Some authors call a graph by the longer term ``undirected graph'' and simply use the following definition of a directed graph as a graph. However when using Definition 1 of a graph, it is standard practice to abbreviate the phrase ``directed graph'' (as done below in Definition 2) with the word digraph.Definition: digraphA digraph G=(V,E) is a finite nonempty set V of vertices together with a (possibly empty) set E of ordered pairs of vertices of G called arcs. An arc that begins and ends at a same vertex u is called a loop. We usually (but not always) disallow loops in our digraphs.By being defined as a set, E does not contain duplicate (or multiple) edges/arcs between the same two vertices. For a given graph (or digraph) G we also denote the set of vertices by V(G) and the set of edges (or arcs) by E(G) to lessen any ambiguity.Definition: order, sizeThe order of a graph (digraph) G=(V,E) is |V|, sometimes denoted by |G| , and the size of this graph is |E| . Sometimes we view a graph as a digraph where every unordered edge (u,v) is replaced by two directed arcs (u,v) and (v,u) . In this case, the size of a graph is half the size of the corresponding digraph.ExampleG1 is a graph of order 5G2 is a digraph of order 5The size of G1 is 6 where E(G1) = {(0, 1), (0, 2), (1, 2), (2, 3), (2, 4), (3, 4)}The size of the digraph G2 is 7 where E(G2) = {(0, 2), (1, 0), (1, 2), (1, 3), (3, 1), (3, 4), (4, 2)}.Definition: walk, length, path, cycleA walk in a graph (digraph) G is a sequence of vertices v0, v1, … vn such that, for all 0 <= i< n , (vi, vi+1) is an edge (arc) in G . The length of the walk v0, v1, … vn is the number n (i.e., number of edges/arcs). A path is a walk in which no vertex is repeated. A cycle is a walk (of length at least three for graphs) in which v0 =vn and no other vertex is repeated; sometimes, if it is understood, we omit vn from the sequence.Example walksWalks in G1:0,1,2, 3, 40,1,2,00,1,20,1,0Walks in G2:3,1,21,3,13,1,3,1,0Example pathsPaths in G1:0,1,2, 3, 40,1,2Paths in G2:3,1,2Example cyclesCycles in G1:0,1,2,00,1,2 (understood)Cycles in G2:1,3,1Definition: connected, strongly connectedA graph G is connected if there is a path between all pairs of vertices u and v of V(G) . A digraph G is strongly connected if there is a path from vertex u to vertex v for all pairs u and v in V(G).Connected?G1 is connectedG2 is not strongly connected.No arcs leaving vertex 2Definition: degreeIn a graph, the degree of a vertex v , denoted by deg(v), is the number of edges incident to v . in-degree == out-degreeFor digraphs, the out-degree of a vertex v is the number of arcs {(v,z) € E| z € V} incident from v (leaving v ) and the in-degree of vertex v is the number of arcs {(z,v) € E| z € V} incident to v (entering v ).Degree, degree sequenceG1:deg(0) = 2deg(1) = 2 deg(2) = 4 deg(3) = 2 Deg(4) = 2Degree sequence = (2,2,4,2,2)Degree, degree sequenceG2:In-degree sequence = (1,1,3,1,1)Out-degree sequence = (1,3,0,2,1)Degree of vertex of a digraph sometimes written as sum of in-degree and out-degree:(2,4,3,3,2)Definition: diameterThe diameter of a connected graph or strongly connected digraph G=(V,E) is the least integer D such that for all vertices u and v in G we have d(u,v) <=D, where d(u,v) denotes the distance from u to v in G, that is, the length of a shortest path between u and v.DiameterG1:min(d(u,v) )= 2Diameter = 2 G2: not strongly connected, diameter not definedComputer representationsadjacency matrices For a graph G of order n , an adjacency matrix representation is a boolean matrix (often encoded with 0's and 1's) of dimension n such that entry (i,j) is true if and only if edge/arc (I,j) is in E(G).adjacency listsFor a graph G of order n , an adjacency lists representation is n lists such that the i-th list contains a sequence (often sorted) of out-neighbours of vertex i of G .Adjacency matrices for G1,G2Adjacency lists for G1,G2For digraphs, stores only the out-edgesMatrix vs. list representationMatrixn vertices and m edges requires O( n2 ) storagecheck if edge/arc (i,j) is in graph – O(1)Listn vertices and m edges, requires O(m) storagePreferable for sparse graphstcheck if edge/arc (i,j) is in graph - O(n) timeNote: other specialized representations