CompSci 102 © Michael Frank16.1Today’s topics••GraphsGraphs––Basics & typesBasics & types––PropertiesProperties––ConnectivityConnectivity––Hamilton & Euler PathsHamilton & Euler Paths••Reading: Sections Reading: Sections 8.1-8.58.1-8.5CompSci 102 © Michael Frank16.2Simple Graphs••Correspond to symmetric,Correspond to symmetric,irreflexiveirreflexive binary relations binary relations RR..••A A simple graphsimple graph GG=(=(VV,,EE))consists of:consists of:––a set a set VV of of verticesvertices or or nodes nodes ( (VV corresponds to corresponds tothe universe of the relation the universe of the relation RR),),––a set a set EE of of edgesedges / / arcsarcs / / linkslinks: unordered pairs: unordered pairsof of [distinct][distinct] elements elements uu,,vv VV, such that , such that uRvuRv..Visual Representationof a Simple GraphCompSci 102 © Michael Frank16.3••Let Let VV be the set of states in the far- be the set of states in the far-southeastern U.S.:southeastern U.S.:––I.e., I.e., VV={FL, GA, AL, MS, LA, SC, TN, NC}={FL, GA, AL, MS, LA, SC, TN, NC}••Let Let EE={{={{uu,,vv}|}|u u adjoins adjoins vv}}={{FL,GA},{FL,AL},{FL,MS},={{FL,GA},{FL,AL},{FL,MS}, {FL,LA},{GA,AL},{AL,MS}, {FL,LA},{GA,AL},{AL,MS}, {MS,LA},{GA,SC},{GA,TN}, {MS,LA},{GA,SC},{GA,TN}, {SC,NC},{NC,TN},{MS,TN}, {SC,NC},{NC,TN},{MS,TN}, {MS,AL}} {MS,AL}}Example of a Simple GraphTNALMSLASCGAFLNCCompSci 102 © Michael Frank16.4Graph example••Can the edge weights below be correct forCan the edge weights below be correct forany group of cities?any group of cities?CompSci 102 © Michael Frank16.5Multigraphs••Like simple graphs, but there may be Like simple graphs, but there may be moremorethan onethan one edge connecting two given nodes. edge connecting two given nodes.••A A multigraphmultigraph GG=(=(VV, , EE, , f f )) consists of a set consists of a setVV of vertices, a set of vertices, a set EE of edges (as primitive of edges (as primitiveobjects), and a functionobjects), and a functionff::EE{{{{uu,,vv}|}|uu,,vv VV uuvv}}..••E.g.E.g., nodes are cities, edges, nodes are cities, edgesare segments of major highways.are segments of major highways.ParalleledgesCompSci 102 © Michael Frank16.6Pseudographs••Like a Like a multigraphmultigraph, but edges connecting a node to, but edges connecting a node toitself are allowed. itself are allowed. ((RR may be reflexive.) may be reflexive.)••A A pseudographpseudograph GG=(=(VV, , EE, , f f )) where whereff::EE{{{{uu,,vv}|}|uu,,vvVV}}. Edge . Edge eeEE is a is a looploop if ifff((ee)={)={uu,,uu}={}={uu}}..••E.g.E.g., nodes are campsites, nodes are campsitesin a state park, edges arein a state park, edges arehiking trails through thehiking trails through thewoods.woods.CompSci 102 © Michael Frank16.7Directed Graphs••Correspond to arbitrary binary relations Correspond to arbitrary binary relations RR,,which need not be symmetric.which need not be symmetric.••A A directed graphdirected graph ( (VV,,EE) consists of a set of) consists of a set ofvertices vertices VV and a binary relation and a binary relation EE on on VV..••E.g.E.g.: : VV = set of People, = set of People,EE={(={(xx,,yy) | ) | xx loves loves yy}}CompSci 102 © Michael Frank16.8Directed Multigraphs••Like directed graphs, but there may beLike directed graphs, but there may bemore than one arc from a node to another.more than one arc from a node to another.••A A directed directed multigraphmultigraph GG=(=(VV, , EE, , f f )) consists consistsof a set of a set VV of vertices, a set of vertices, a set EE of edges, and of edges, anda function a function ff::EEVVVV..••E.g.E.g., , VV=web pages,=web pages,EE=hyperlinks. =hyperlinks. The WWW isThe WWW isa directed a directed multigraphmultigraph......CompSci 102 © Michael Frank16.9Types of Graphs: Summary••Summary of the bookSummary of the book’’s definitions.s definitions.••Keep in mind this terminology is not fullyKeep in mind this terminology is not fullystandardized across different authors...standardized across different authors...TermEdgetypeMultipleedges ok?Self-loops ok?Simple graph Undir. No NoMultigraph Undir. Yes NoPseudograph Undir. Yes YesDirected graph Directed No YesDirected multigraph Directed Yes YesCompSci 102 © Michael Frank16.10§8.2: Graph TerminologyYou need to learn the following terms:You need to learn the following terms:••Adjacent, connects, endpoints, degree,Adjacent, connects, endpoints, degree,initial, terminal, in-degree, out-degree,initial, terminal, in-degree, out-degree,complete, cycles, wheels, n-cubes, bipartite,complete, cycles, wheels, n-cubes, bipartite,subgraphsubgraph, union., union.CompSci 102 © Michael Frank16.11AdjacencyLet Let GG be an undirected graph with edge set be an undirected graph with edge set EE..Let Let eeEE be (or map to) the pair be (or map to) the pair {{uu,,vv}}. Then. Thenwe say:we say:••uu, , vv are are adjacentadjacent / / neighborsneighbors / / connectedconnected..••Edge Edge ee is is incident withincident with vertices vertices uu and and vv..••Edge Edge ee connectsconnects uu and and vv..••Vertices Vertices uu and and vv are are endpointsendpoints of edge of edge ee..CompSci 102 © Michael Frank16.12Degree of a Vertex••Let Let GG be an undirected graph, be an undirected graph, vvVV a vertex. a vertex.••The The degreedegree of of vv, , deg(deg(vv)), is its number of, is its number ofincident edges. (Except that any self-loopsincident edges. (Except that any self-loopsare counted twice.)are counted twice.)••A vertex with degree 0 is called A vertex with degree 0 is called isolatedisolated..••A vertex of degree 1 is called A vertex of degree 1 is called pendantpendant..CompSci 102 © Michael Frank16.13Handshaking Theorem••Let Let GG be an undirected (simple, multi-, or be an undirected (simple, multi-, orpseudo-) graph with vertex set pseudo-) graph with vertex set VV and edge and edgeset set EE. Then. Then••Corollary: Corollary: Any undirected graph has anAny undirected graph has aneven number of vertices of odd degree.even number of vertices of odd degree.EvVv2)deg( =CompSci 102 © Michael Frank16.14Directed Adjacency••Let Let GG be a directed (possibly multi-) graph, be a directed (possibly multi-) graph,and let
View Full Document
Unlocking...