Graph TerminologyReadingWhat are graphs?GraphsVarietiesMotivation for GraphsSlide 7CSE Course Prerequisites at UWRepresenting a MazeRepresenting Electrical CircuitsProgram statementsPrecedenceInformation Transmission in a Computer NetworkTraffic Flow on HighwaysGraph DefinitionGraph ExampleDirected vs Undirected GraphsUndirected TerminologySlide 19Directed TerminologySlide 21Handshaking TheoremGraph RepresentationsAdjacency MatrixAdjacency Matrix for a DigraphAdjacency ListAdjacency List for a DigraphGraph TerminologyCSE 373Data StructuresLecture 1312/26/03 Graph Terminology - Lecture 13 2Reading•Reading ›Section 9.112/26/03 Graph Terminology - Lecture 13 3What are graphs?•Yes, this is a graph….•But we are interested in a different kind of “graph”12/26/03 Graph Terminology - Lecture 13 4Graphs •Graphs are composed of›Nodes (vertices)›Edges (arcs)nodeedge12/26/03 Graph Terminology - Lecture 13 5Varieties•Nodes›Labeled or unlabeled•Edges›Directed or undirected›Labeled or unlabeled12/26/03 Graph Terminology - Lecture 13 6Motivation for Graphs•Consider the data structures we have looked at so far…•Linked list: nodes with 1 incoming edge + 1 outgoing edge•Binary trees/heaps: nodes with 1 incoming edge + 2 outgoing edges•B-trees: nodes with 1 incoming edge + multiple outgoing edges1096999497ValueNextnodeValueNextnode3 512/26/03 Graph Terminology - Lecture 13 7Motivation for Graphs•How can you generalize these data structures?•Consider data structures for representing the following problems…12/26/03 Graph Terminology - Lecture 13 8CSE Course Prerequisites at UW321143142322326341370378401421Nodes = coursesDirected edge = prerequisite37341041341541746112/26/03 Graph Terminology - Lecture 13 9Representing a MazeSNodes = roomsEdge = door or passageSEBE12/26/03 Graph Terminology - Lecture 13 10Representing Electrical CircuitsNodes = battery, switch, resistor, etc.Edges = connectionsBatterySwitchResistor12/26/03 Graph Terminology - Lecture 13 11Program statementsx1=q+y*zx2=y*z-qNaive:commonsubexpressioneliminated:y z*-q+q*x1 x2y z-q+q *x1 x2Nodes = symbols/operatorsEdges = relationshipsy*z calculated twice12/26/03 Graph Terminology - Lecture 13 12PrecedenceS1a=0;S2b=1;S3c=a+1S4d=b+a;S5e=d+1;S6e=c+d;312654Which statements must execute before S6?S1, S2, S3, S4Nodes = statementsEdges = precedence requirements12/26/03 Graph Terminology - Lecture 13 13Information Transmission in a Computer NetworkSeattleNew YorkL.A.TokyoSydneySeoulNodes = computersEdges = transmission rates12814018130165612/26/03 Graph Terminology - Lecture 13 14Traffic Flow on HighwaysNodes = citiesEdges = # vehicles on connecting highwayUW12/26/03 Graph Terminology - Lecture 13 15Graph Definition•A graph is simply a collection of nodes plus edges›Linked lists, trees, and heaps are all special cases of graphs•The nodes are known as vertices (node = “vertex”)•Formal Definition: A graph G is a pair (V, E) where›V is a set of vertices or nodes ›E is a set of edges that connect vertices12/26/03 Graph Terminology - Lecture 13 16Graph Example•Here is a directed graph G = (V, E)›Each edge is a pair (v1, v2), where v1, v2 are vertices in V ›V = {A, B, C, D, E, F}E = {(A,B), (A,D), (B,C), (C,D), (C,E), (D,E)}ABCEDF12/26/03 Graph Terminology - Lecture 13 17Directed vs Undirected Graphs•If the order of edge pairs (v1, v2) matters, the graph is directed (also called a digraph): (v1, v2)  (v2, v1) •If the order of edge pairs (v1, v2) does not matter, the graph is called an undirected graph: in this case, (v1, v2) = (v2, v1) v1v2v1v212/26/03 Graph Terminology - Lecture 13 18Undirected Terminology•Two vertices u and v are adjacent in an undirected graph G if {u,v} is an edge in G›edge e = {u,v} is incident with vertex u and vertex v•The degree of a vertex in an undirected graph is the number of edges incident with it›a self-loop counts twice (both ends count)›denoted with deg(v)12/26/03 Graph Terminology - Lecture 13 19Undirected TerminologyABCEDFDegree = 3Degree = 0B is adjacent to C and C is adjacent to B(A,B) is incidentto A and to BSelf-loop12/26/03 Graph Terminology - Lecture 13 20Directed Terminology•Vertex u is adjacent to vertex v in a directed graph G if (u,v) is an edge in G›vertex u is the initial vertex of (u,v)•Vertex v is adjacent from vertex u›vertex v is the terminal (or end) vertex of (u,v)•Degree›in-degree is the number of edges with the vertex as the terminal vertex›out-degree is the number of edges with the vertex as the initial vertex12/26/03 Graph Terminology - Lecture 13 21Directed TerminologyABCEDFIn-degree = 2Out-degree = 1In-degree = 0Out-degree = 0B adjacent to C and C adjacent from B12/26/03 Graph Terminology - Lecture 13 22Handshaking Theorem•Let G=(V,E) be an undirected graph with |E|=e edges. Then•Every edge contributes +1 to the degree of each of the two vertices it is incident with ›number of edges is exactly half the sum of deg(v)›the sum of the deg(v) values must be evenVvdeg(v)2eAdd up the degrees of all vertices.12/26/03 Graph Terminology - Lecture 13 23•Space and time are analyzed in terms of:•Number of vertices = |V| and•Number of edges = |E|•There are at least two ways of representing graphs:•The adjacency matrix representation•The adjacency list representationGraph Representations12/26/03 Graph Terminology - Lecture 13 24A B C D E F0 1 0 1 0 0 1 0 1 0 0 0 0 1 0 1 1 0 1 0 1 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 M(v, w) = 1 if (v, w) is in E0 otherwiseABCDEFSpace = |V|2ABCEDFAdjacency Matrix12/26/03 Graph Terminology - Lecture 13 25A B C D E F0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 ABCDEFSpace = |V|2M(v, w) = 1 if (v, w) is in E0 otherwiseABCEDFAdjacency Matrix for a Digraph12/26/03 Graph Terminology - Lecture 13 26BDB DCACEDEACABCDEFABCEDFSpace = a |V| + 2 b |E|For each v in V, L(v) = list of w such that (v, w) is in EabAdjacency Listlist ofneighbors12/26/03 Graph Terminology - Lecture 13 27BDEDCabABCDEFEABCEDFFor each v in V, L(v) = list of w such that (v, w) is in