Based on slides by Y. Peng University of MarylandRepresenting GraphsSlide 3Slide 4Slide 5Slide 6Isomorphism of GraphsSlide 8Slide 9Slide 10Slide 11ExamplesConnectivitySlide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Cut vertices and edgesSlide 22Slide 23Slide 24Slide 251Representing Graphs andGraph Isomorphism(Chapter 9.3) Connectivity (Chapter 9.4)Based on slides by Y. PengUniversity of MarylandUniversity of Maryland2Representing GraphsRepresenting Graphsaabbccddaabbccdda, da, dbba, da, dcca, b, ca, b, cddb, c, db, c, daaAdjacent Adjacent VerticesVerticesVertexVertexaabbcca, b, ca, b, cddccaaTerminal Terminal VerticesVerticesInitial Initial VertexVertex3Representing GraphsRepresenting GraphsDefinition:Definition: Let G = (V, E) be a simple graph Let G = (V, E) be a simple graph with |V| = n. Suppose that the vertices of G are with |V| = n. Suppose that the vertices of G are listed in arbitrary order as vlisted in arbitrary order as v11, v, v22, …, v, …, vnn. . The The adjacency matrixadjacency matrix A (or A A (or AGG) of G, with ) of G, with respect to this listing of the vertices, is the nrespect to this listing of the vertices, is the nn n zero-one matrix with 1 as its (i, j) entry when vzero-one matrix with 1 as its (i, j) entry when vii and vand vjj are adjacent, and 0 otherwise. are adjacent, and 0 otherwise.In other words, for an adjacency matrix A = [aIn other words, for an adjacency matrix A = [aijij], ], aaijij = 1 = 1 if {vif {vii, v, vjj} is an edge of G,} is an edge of G,aaijij = 0 = 0otherwise.otherwise.4Representing GraphsRepresenting GraphsaabbccddExample:Example: What is the What is the adjacency matrix Aadjacency matrix AGG for the for the following graph G based on following graph G based on the order of vertices a, b, c, the order of vertices a, b, c, d ?d ?Solution:Solution:0111100110011110GANote:Note: Adjacency matrices of undirected graphs Adjacency matrices of undirected graphs are always symmetric.are always symmetric.5Representing GraphsRepresenting GraphsDefinition:Definition: Let G = (V, E) be an undirected Let G = (V, E) be an undirected graph with |V| = n. Suppose that the vertices graph with |V| = n. Suppose that the vertices and edges of G are listed in arbitrary order as vand edges of G are listed in arbitrary order as v11, , vv22, …, v, …, vn n and eand e11, e, e22, …, e, …, emm, respectively. , respectively. The The incidence matrixincidence matrix of G with respect to this of G with respect to this listing of the vertices and edges is the nlisting of the vertices and edges is the nm m zero-one matrix with 1 as its (i, j) entry when zero-one matrix with 1 as its (i, j) entry when edge eedge ejj is incident with v is incident with vii, and 0 otherwise., and 0 otherwise.In other words, for an incidence matrix M = [mIn other words, for an incidence matrix M = [mijij], ], mmijij = 1 = 1 if edge eif edge ejj is incident with v is incident with vii mmijij = 0 = 0otherwise.otherwise.6Representing GraphsRepresenting GraphsExample:Example: What is the What is the incidence matrix M for the incidence matrix M for the following graph G based on following graph G based on the order of vertices a, b, c, d the order of vertices a, b, c, d and edges 1, 2, 3, 4, 5, 6?and edges 1, 2, 3, 4, 5, 6?Solution:Solution:001110111000000101010011MNote:Note: Incidence matrices of directed graphs contain two 1s Incidence matrices of directed graphs contain two 1s per column for edges connecting two vertices and one 1 per per column for edges connecting two vertices and one 1 per column for loops.column for loops.aabbccdd1122445533667Isomorphism of GraphsIsomorphism of GraphsDefinition:Definition: The simple graphs G The simple graphs G11 = (V = (V11, E, E11) and ) and GG22 = (V = (V22, E, E22) are ) are isomorphicisomorphic if there is a if there is a bijection (an one-to-one and onto function) f bijection (an one-to-one and onto function) f from Vfrom V11 to V to V22 with the property that a and b are with the property that a and b are adjacent in Gadjacent in G11 if and only if f(a) and f(b) are if and only if f(a) and f(b) are adjacent in Gadjacent in G22, for all a and b in V, for all a and b in V11..Such a function f is called an Such a function f is called an isomorphismisomorphism..In other words, GIn other words, G11 and G and G22 are isomorphic if their are isomorphic if their vertices can be ordered in such a way that the vertices can be ordered in such a way that the adjacency matrices Madjacency matrices MGG11 and M and MGG22 are identical. are identical.8Isomorphism of GraphsIsomorphism of GraphsFrom a visual standpoint, GFrom a visual standpoint, G11 and G and G22 are are isomorphic if they can be arranged in such a isomorphic if they can be arranged in such a way that their way that their displays are identicaldisplays are identical (of (of course without changing adjacency).course without changing adjacency).Unfortunately, for two simple graphs, each with Unfortunately, for two simple graphs, each with n vertices, there are n vertices, there are n! possible n! possible isomorphismsisomorphisms that we have to check in order that we have to check in order to show that these graphs are isomorphic.to show that these graphs are isomorphic.However, showing that two graphs are However, showing that two graphs are notnot isomorphic can be easy.isomorphic can be easy.9Isomorphism of GraphsIsomorphism of GraphsFor this purpose we can check For this purpose we can check invariantsinvariants, that is, , that is, properties that two isomorphic simple graphs must properties that two isomorphic simple graphs must both have.both have.For example, they must haveFor example, they must have• the same number of vertices,the same number of vertices,• the same number of edges, andthe same number of edges, and• the same degrees of vertices.the same degrees of vertices.Note that two graphs that Note that two graphs that differdiffer in any of these in any of these invariants are not isomorphic, but two graphs that invariants are not isomorphic, but two graphs that matchmatch in all of them are not necessarily in all of them are not necessarily isomorphic.isomorphic.10Isomorphism of GraphsIsomorphism of GraphsExample I:Example I: Are the following two graphs isomorphic? Are the following two graphs