Applied Combinatorics, 4th Ed.Alan Tucker.ppt

1、1/25/2005,Tucker, Sec. 1.2,1,Applied Combinatorics, 4th Ed. Alan Tucker,Section 1.2 IsomorphismPrepared by Jo Ellis-Monaghan,1/25/2005,Tucker, Sec. 1.2,2,Two graphs G and are isomorphic if :There exists a one-to-one correspondence between vertices in G and , such thatThere is an edge between a and b

2、 in G if and only if there is an edge between the corresponding vertices and in .The definition for oriented graphs is the same, except the head and tail of each edge of G must correspond to the head and tail in .,Definition of Isomorphism,1/25/2005,Tucker, Sec. 1.2,3,Example of isomorphic graphs,a,

3、b,c,d,e,f,1,2,3,4,5,6,G,1/25/2005,Tucker, Sec. 1.2,4,Kn, the complete graph on n vertices,K2,K3,K5,K8,K4,K1,1/25/2005,Tucker, Sec. 1.2,5,The complement of a graph,The complement of G has all the edges that are missing in Gi.e. that would have to be added to make the complete graph.,G,1/25/2005,Tucke

4、r, Sec. 1.2,6,Advantage of the complement,Theorem:Two graphs, G and H, are isomorphic if and only if their complements are.In practice this means that we work with whichever of G or has few edges.,1/25/2005,Tucker, Sec. 1.2,7,Subgraphs,Definition: if G is a graph, a subgraph H of G consists of a sub

5、set V of the vertices of G, and a subset of the edges of G with endpoints in V.,c,d,e,i,j,k,f,l,Two subgraphs of G,1/25/2005,Tucker, Sec. 1.2,8,Induced subgraphs,Choose a subset of the vertices of G, then include only the edges among those vertices.,n,a,b,c,d,e,f,g,h,i,j,k,l,m,o,A graph G,Subgraph i

6、nduced by the vertices of degree 4.,1/25/2005,Tucker, Sec. 1.2,9,Elementary properties of isomorphic graphs,Edge and vertex counts Isomorphic graphs have the same number of edges and vertices.Vertex sequence (the list of vertex degrees) Isomorphic graphs have the same vertex sequences.Warning! These

7、 can be used to show two graphs are not isomorphic, but can not show that two graphs are isomorphic.,1/25/2005,Tucker, Sec. 1.2,10,Two non-isomorphic graphs,Vertices: 6 Edges: 7 Vertex sequence: 4, 3, 3, 2, 2, 0.,Vertices: 6 Edges: 7 Vertex sequence: 5, 3, 2, 2, 1, 1.,1/25/2005,Tucker, Sec. 1.2,11,S

8、ubgraph properties of isomorphic graphs,Isomorphic graphs have the same sets of subgraphs:there is a one-to-one correspondence between the subgraphs such that corresponding subgraphs are isomorphic.Typically check induced subgraphs, or number of a specific kind of subgraphs such as cycles or cliques

9、.Warning! These can be used to show two graphs are not isomorphic, but can not show that two graphs are isomorphic.,1/25/2005,Tucker, Sec. 1.2,12,Two non-isomorphic graphs,a,c,d,2,3,5,6,7,8,1,4,Vertices: 8 Edges: 10 Vertex sequence: 3, 3, 3, 3, 2, 2, 2, 2.,Vertices: 8 Edges: 10 Vertex sequence: 3, 3

10、, 3, 3, 2, 2, 2, 2.,However, induced subgraphs on degree 3 vertices are NOT isomorphic!,3,1/25/2005,Tucker, Sec. 1.2,13,An approach to checking isomorphism:,Count the vertices. The graphs must have an equal number.Count the edges. The graphs must have an equal number.Check vertex degree sequence. Ea

11、ch graph must have the same degree sequence.Check induced subgraphs for isomorphism. If the subgraphs are not isomorphic, then the larger graphs are not either. Count numbers of cycles/cliques. If these tests dont help, and you suspect the graphs actually are isomorphic, then try to find a one-to-on

12、e correspondence between vertices of one graph and vertices of the other. Remember that a vertex of degree n in the one graph must correspond to a vertex of degree n in the other.,1/25/2005,Tucker, Sec. 1.2,14,For the class to try:,a,b,f,e,c,d,1,2,3,4,5,6,Are these pairs of graphs isomorphic?,#1,#2,Isomorphic: a-1, b-5, c-4, d-3, e-2, f-6.,Not Isomorphic: 5 K3s on left, 4 K3s on right.,a,b,c,d,f,g,e,1,2,3,4,5,6,7,