第8章图的基本概念 4同构 由于在画图的图形时,顶点的位置和边的几何形 状是无关紧要的,因此表面上完全不同的图形可能表 示的是一个图。为了判断不同的图形是否反映同一个 图形的性质,我们给出图的同构的概念
第8章 图的基本概念 4.同构 由于在画图的图形时，顶点的位置和边的几何形 状是无关紧要的，因此表面上完全不同的图形可能表 示的是一个图。为了判断不同的图形是否反映同一个 图形的性质，我们给出图的同构的概念
第8章图的基本概念 定义814设有两个图G1=(V1,E1〉,G2=〈V2, E2),如果存在着双射:V1→V2,使得(v,v)∈E1 当且仅当(f(v),f(v))∈E2(或者(v,v ∈E1当且仅当(f(v),f(v)〉∈E2)且它们的重 数相同,则称图G1与G2同构,记作G1≡G2 例如,图8.14中G1签G2,其中 f:V1→V2,f(v)=1(1,2,…,6)。G3=G4,其 中:V1→V2,f(v1)=l,f(n2)=1,f(V3)=2
第8章 图的基本概念 定义8.1.4 设有两个图G1 =〈V1，E1〉，G2 =〈V2， E2〉，如果存在着双射f：V1→V2，使得（vi，vj）∈E1 当且仅当（f（vi），f（vj））∈E2（或者〈vi，vj〉 ∈E1当且仅当〈f（vi），f（vj）〉∈E2）且它们的重 数相同，则称图G1与G2同构，记作G1 G2。 例如，图8.1.4中G1 G2，其中 f：V1→V2，f（vi）=ui（i=1，2，…，6）。G3 G4，其 中f：V1→V2，f（v1）=u3，f（v2）=u1，f（v3）=u2。
第8章图的基本概念 图8.1.4
第8章 图的基本概念 图 8.1.4 G1 G2 G3 G4 u1 u3 u5 u2 u4 u6 u 1 u2 u3 1 2 3 4 5 6 1 2 3
第8章图的基本概念 容易看出,两个同构的图必定满足:顶点数相同 边数相同、度数列相同。但这是二图同构的必要条件 而非充分条件,如图81.5中的(a)、(b)均为6阶3 正则图,满足上述三个条件,但因为对于图(a)中的 任一顶点,与该点关联的三个顶点间彼此不邻接,而 对于图(b)中的任一顶点,与该点关联的三个顶点中 有两个是邻接点,所以它们不同构。同样可以看出图 (c)、(d)也是不同构的
第8章 图的基本概念 容易看出，两个同构的图必定满足：顶点数相同、 边数相同、度数列相同。但这是二图同构的必要条件 而非充分条件，如图8.1.5中的（a）、（b）均为6阶3- 正则图，满足上述三个条件，但因为对于图（a）中的 任一顶点，与该点关联的三个顶点间彼此不邻接，而 对于图（b）中的任一顶点，与该点关联的三个顶点中 有两个是邻接点，所以它们不同构。同样可以看出图 （c）、（d）也是不同构的
第8章图的基本概念 (b) 图8.1.5
第8章 图的基本概念 图 8.1.5 (a) (b) (c) (d)