离散数学(第10章)陈瑜

1、2022-5-42022-5-4计算机科学与工程学院计算机科学与工程学院1 1陈瑜陈瑜Email：2022-5-42022-5-42022-5-4计算机科学与工程学院计算机科学与工程学院2 2期中考试通知期中考试通知n期中考试：期中考试：随堂闭卷随堂闭卷考试考试 （独立答题、严禁作弊）（独立答题、严禁作弊）n时间：第时间：第11周周四周周四n考试范围：前考试范围：前6章所学内容。章所学内容。n课序号课序号2:周周4（11月月19日）上午第日）上午第1大节。大节。 课序号课序号3:周周4（11月月19日）下午第日）下午第1大节。大节。n望相互转告，望相互转告，2022-5-42022-5-4计算

2、机科学与工程学院计算机科学与工程学院3 31010. .1 1 图的基本概念图的基本概念2022-5-42022-5-4计算机科学与工程学院计算机科学与工程学院4 4主要内容主要内容n 图的基本概念图的基本概念什么是图什么是图图的分类图的分类结点的度数结点的度数 握手定理握手定理子图与补图子图与补图 完全图完全图补图补图 图的同构图的同构2022-5-42022-5-4计算机科学与工程学院计算机科学与工程学院5 51010.1.1 图的基本概念图的基本概念n 无序积的定义：无序积的定义：设设A,B A,B 为任意集合，称集合为任意集合，称集合A&B A&B (a,b)|aA (

3、a,b)|aA ，bBbB为为A A 与与B B 的的无序无序积积 ，（，（a,b a,b ） 称为称为无序对无序对 。n 与序偶不同，无论与序偶不同，无论a,ba,b是否相等，均有：是否相等，均有： (a,b)(a,b)(b,a)(b,a)。 2022-5-42022-5-4计算机科学与工程学院计算机科学与工程学院6 61010.1.1 图的基本概念图的基本概念n 无序积的定义：设A,B 为任意集合，称集合A&B (a,b)|aA ，bB为A 与B 的无序积 ，（a,b ） 称为无序对 。n 与序偶不同，无论与序偶不同，无论a,ba,b是否相等，均有：是否相等，均有： (a,b)(a

4、,b)(b,a)(b,a)。 2022-5-42022-5-4计算机科学与工程学院计算机科学与工程学院7 7图的定义图的定义n 定义定义10.110.1 一个一个图图是一个序偶是一个序偶(V,E)(V,E)，记为，记为 G G(V,E)(V,E)，其中：，其中： 1 1）V V（G G）vv1 1,v,v2 2,v,v3 3,v,vn n 是一个有限的非空集合，是一个有限的非空集合，v vi i(i(i1,2,3,n)1,2,3,n)称为称为结点结点, ,简称简称点点，V V为为结点集结点集； 2 2）E E（G G）ee1 1,e,e2 2,e,e3 3,e,em m 是一个有限的集合，是一

5、个有限的集合，e ei i(i(i1,2,3,m)1,2,3,m)称为边，称为边，E E为边集，为边集，E E中的每个元素都是中的每个元素都是由由V V中不同结点所构成的无序对，且不含重复元素。中不同结点所构成的无序对，且不含重复元素。 3 3）图）图G G的结点数称为的结点数称为G G的阶，用的阶，用n n表示，表示，G G的边数用的边数用m m表示，表示，也可表示成也可表示成 (G)=m(G)=m 。 2022-5-42022-5-4计算机科学与工程学院计算机科学与工程学院8 8图的定义图的定义n 定义定义10.110.1 一个一个图图是一个序偶是一个序偶(V,E)(V,E)，记为，记为

6、G G(V,E)(V,E)，其中：，其中： 1 1）V（G）v1,v2,v3,vn是一个有限的非空集合，vi(i1,2,3,n)称为结点,简称点，V为结点集； 2 2）E E（G G）ee1 1,e,e2 2,e,e3 3,e,em m 是一个有限的集合，是一个有限的集合，e ei i(i(i1,2,3,m)1,2,3,m)称为称为边边，E E为为边集边集，E E中的每个元素都是中的每个元素都是由由V V中不同结点所构成的无序对，且不含重复元素。中不同结点所构成的无序对，且不含重复元素。 3 3）图）图G G的结点数称为的结点数称为G G的阶，用的阶，用n n表示，表示，G G的边数用的边数用

7、m m表示，表示，也可表示成也可表示成 (G)=m(G)=m 。2022-5-42022-5-4计算机科学与工程学院计算机科学与工程学院9 9图的定义图的定义n 定义定义10.110.1 一个一个图图是一个序偶是一个序偶(V,E)(V,E)，记为，记为 G G(V,E)(V,E)，其中：，其中： 1 1）V（G）v1,v2,v3,vn是一个有限的非空集合，vi(i1,2,3,n)称为结点,简称点，V为结点集； 2 2）E（G）e1,e2,e3,em是一个有限的集合，ei(i1,2,3,m)称为边，E为边集，E中的每个元素都是由V中不同结点所构成的无序对，且不含重复元素。 3 3）图图G G的结

8、点数称为的结点数称为G G的的阶阶，用，用n n表示，表示，G G的边数用的边数用m m表示，表示，也可表示成也可表示成 (G)=m(G)=m 。 2022-5-42022-5-4计算机科学与工程学院计算机科学与工程学院1010图的分类图的分类( (按边的方向按边的方向) )若边若边e e与无序结点对与无序结点对(u(u，v)v)相对应，则称边相对应，则称边e e为为无向边无向边, ,记为记为e e(u(u，v)v)，这时称这时称u u，v v是边是边e e的两个的两个端点端点；若边若边e e与有序结点对与有序结点对uv相对应，则称边相对应，则称边e e为有向边，为有向边，记为记为e euv，

9、这时称这时称u u是边是边e e的始点。的始点。v v是边是边e e的终的终点，统称为点，统称为e e的端点；的端点；e e是是u u的出边，是的出边，是v v的入边。的入边。每条边都是无向边的图称为无向图；每条边都是无向边的图称为无向图；每条边都是有向边的图称为有向图；每条边都是有向边的图称为有向图；有些边是无向边，而另一些是有向边的图称为混合图。有些边是无向边，而另一些是有向边的图称为混合图。n用小圆圈表示用小圆圈表示V V中的结点，用由中的结点，用由u u指向指向v v的有向线段表示的有向线段表示，无向线段表示，无向线段表示(u,v)(u,v)。2022-5-42022-5-4计算机科学

10、与工程学院计算机科学与工程学院1111图的分类图的分类( (按边的方向按边的方向) )若边e与无序结点对(u，v)相对应，则称边e为无向边,记为e(u，v)，这时称u，v是边e的两个端点；若边若边e e与有序结点对与有序结点对uv相对应，则称边相对应，则称边e e为为有向边有向边，记为记为e euv，这时称这时称u u是边是边e e的的始点始点。v v是边是边e e的的终终点点，统称为，统称为e e的的端点端点；e e是是u u的出边，是的出边，是v v的入边。的入边。每条边都是无向边的图称为无向图；每条边都是无向边的图称为无向图；每条边都是有向边的图称为有向图；每条边都是有向边的图称为有向图

11、；有些边是无向边，而另一些是有向边的图称为混合图。有些边是无向边，而另一些是有向边的图称为混合图。n用小圆圈表示用小圆圈表示V V中的结点，用由中的结点，用由u u指向指向v v的有向线段表示的有向线段表示，无向线段表示，无向线段表示(u,v)(u,v)。2022-5-42022-5-4计算机科学与工程学院计算机科学与工程学院1212图的分类图的分类( (按边的方向按边的方向) )若边e与无序结点对(u，v)相对应，则称边e为无向边,记为e(u，v)，这时称u，v是边e的两个端点；若边e与有序结点对相对应，则称边e为有向边，记为e，这时称u是边e的始点。v是边e的终点，统称为e的端点；e是u的

12、出边，是v的入边。每条边都是无向边的图称为每条边都是无向边的图称为无向图无向图；每条边都是有向边的图称为每条边都是有向边的图称为有向图有向图；有些边是无向边，而另一些是有向边的图称为有些边是无向边，而另一些是有向边的图称为混合图混合图。n用小圆圈表示用小圆圈表示V V中的结点，用由中的结点，用由u u指向指向v v的有向线段表示的有向线段表示，无向线段表示，无向线段表示(u,v)(u,v)。2022-5-42022-5-4计算机科学与工程学院计算机科学与工程学院1313图的分类图的分类( (按边的方向按边的方向) )若边e与无序结点对(u，v)相对应，则称边e为无向边,记为e(u，v)，这时称

13、u，v是边e的两个端点；若边e与有序结点对相对应，则称边e为有向边，记为e，这时称u是边e的始点。v是边e的终点，统称为e的端点；e是u的出边，是v的入边。每条边都是无向边的图称为无向图；每条边都是有向边的图称为有向图；有些边是无向边，而另一些是有向边的图称为混合图。n用用小圆圈小圆圈表示表示V V中的中的结点结点，用由用由u u指向指向v v的的有向线段有向线段表示表示，无向线段无向线段表示表示(u,v)(u,v)。2022-5-42022-5-4计算机科学与工程学院计算机科学与工程学院1414几个概念几个概念在一个图中，关联结点在一个图中，关联结点v vi i和和v vj j的边的边e e

14、，无论是有向的无论是有向的还是无向的，均称边还是无向的，均称边e e与结点与结点v vI I和和v vj j相关联相关联，而，而v vi i和和v vj j称为称为邻接点邻接点，否则称为，否则称为不邻接的不邻接的；关联于同一个结点的两条边称为邻接边；关联于同一个结点的两条边称为邻接边；图中关联同一个结点的边称为环图中关联同一个结点的边称为环( (或自回路或自回路) )；图中不与任何结点相邻接的结点称为孤立结点；图中不与任何结点相邻接的结点称为孤立结点；仅由孤立结点组成的图称为零图；仅由孤立结点组成的图称为零图；仅含一个结点的零图称为平凡图；仅含一个结点的零图称为平凡图；含有含有n n个结点、个

15、结点、m m条边的图条边的图称为称为(n(n，m)m)图；图；e e1 1e e2 2e e5 5v v3 3v v2 2v v1 1e e3 3e e4 4e e6 6v v5 5v v4 42022-5-42022-5-4计算机科学与工程学院计算机科学与工程学院1515几个概念几个概念在一个图中，关联结点vi和vj的边e，无论是有向的还是无向的，均称边e与结点vI和vj相关联，而vi和vj称为邻接点，否则称为不邻接的；关联于同一个结点的两条边称为关联于同一个结点的两条边称为邻接边邻接边；图中关联同一个结点的边称为图中关联同一个结点的边称为环环( (或或自回路自回路) )；图中不与任何结点相

16、邻接的结点称为图中不与任何结点相邻接的结点称为孤立结点孤立结点；仅由孤立结点组成的图称为零图；仅由孤立结点组成的图称为零图；仅含一个结点的零图称为平凡图；仅含一个结点的零图称为平凡图；含有含有n n个结点、个结点、m m条边的图条边的图称为称为(n(n，m)m)图；图；e e1 1e e2 2e e5 5v v3 3v v2 2v v1 1e e3 3e e4 4e e6 6v v5 5v v4 42022-5-42022-5-4计算机科学与工程学院计算机科学与工程学院1616几个概念几个概念在一个图中，关联结点vi和vj的边e，无论是有向的还是无向的，均称边e与结点vI和vj相关联，而vi和

17、vj称为邻接点，否则称为不邻接的；关联于同一个结点的两条边称为邻接边；图中关联同一个结点的边称为环(或自回路)；图中不与任何结点相邻接的结点称为孤立结点；仅由孤立结点组成的图称为仅由孤立结点组成的图称为零图零图；仅含一个结点的零图称为仅含一个结点的零图称为平凡图平凡图；含有含有n n个结点、个结点、m m条边的图条边的图称为称为(n(n，m)m)图图；e e1 1e e2 2e e5 5v v3 3v v2 2v v1 1e e3 3e e4 4e e6 6v v5 5v v4 42022-5-42022-5-4计算机科学与工程学院计算机科学与工程学院1717图的分类图的分类( (按边的重数按

18、边的重数) )在有向图中，两个结点间在有向图中，两个结点间( (包括结点自身间包括结点自身间) )若有同始若有同始点和同终点的几条边，则这几条边称为点和同终点的几条边，则这几条边称为平行边平行边。在无向图中，两个结点间在无向图中，两个结点间( (包括结点自身间包括结点自身间) )若有几条若有几条边，则这几条边称为边，则这几条边称为平行边平行边；含有平行边的图称为多重图；含有平行边的图称为多重图；含有环的多重图称为广义图（伪图）；含有环的多重图称为广义图（伪图）；满足定义满足定义10.110.1的图称为简单图。的图称为简单图。将多重图和广义图中的平行边代之以一条边，去掉环，将多重图和广义图中的平

19、行边代之以一条边，去掉环，可以得到一个简单图，称为原来图的基图。可以得到一个简单图，称为原来图的基图。2022-5-42022-5-4计算机科学与工程学院计算机科学与工程学院1818图的分类图的分类( (按边的重数按边的重数) )在有向图中，两个结点间(包括结点自身间)若有同始点和同终点的几条边，则这几条边称为平行边。在无向图中，两个结点间(包括结点自身间)若有几条边，则这几条边称为平行边；含有平行边的图称为含有平行边的图称为多重图多重图；含有含有环环的多重图称为的多重图称为广义图（伪图）广义图（伪图）；满足定义满足定义10.110.1的图称为的图称为简单图简单图。将多重图和广义图中的平行边代

20、之以一条边，去掉环，将多重图和广义图中的平行边代之以一条边，去掉环，可以得到一个简单图，称为原来图的基图。可以得到一个简单图，称为原来图的基图。2022-5-42022-5-4计算机科学与工程学院计算机科学与工程学院1919图的分类图的分类( (按边的重数按边的重数) )在有向图中，两个结点间(包括结点自身间)若有同始点和同终点的几条边，则这几条边称为平行边。在无向图中，两个结点间(包括结点自身间)若有几条边，则这几条边称为平行边；含有平行边的图称为多重图；含有环的多重图称为广义图（伪图）；满足定义10.1的图称为简单图。将多重图和广义图中的平行边代之以一条边，去掉环，将多重图和广义图中的平行

21、边代之以一条边，去掉环，可以得到一个简单图，称为原来图的可以得到一个简单图，称为原来图的基图。基图。2022-5-42022-5-4计算机科学与工程学院计算机科学与工程学院2020图的分类图的分类( (按权按权) )n赋权图赋权图G G是一个三重组是一个三重组，其中，其中V V是结点集合，是结点集合，E E是边的集合，是边的集合，g g是边是边E E上的权值。非赋权图称为上的权值。非赋权图称为无权无权图图。v v3 3v v2 2v v1 1v v4 45 56 66 67 78 87 79 95 5G G1 12022-5-42022-5-4计算机科学与工程学院计算机科学与工程学院2121结

22、点的度数结点的度数 在在无向图无向图G GVE中，与结点中，与结点v(vv(v V)V)关联的关联的边的条数（边的条数（有环时计算两次有环时计算两次），称为该结点的），称为该结点的度数度数，记为记为deg(v)deg(v)；最大点度和最小点度分别；最大点度和最小点度分别记为记为 和和 。在有向图在有向图G GVE中，以结点中，以结点v v为始点引出的为始点引出的边的条数，称为该结点的出度边的条数，称为该结点的出度, ,记为记为degdeg+ +(v)(v)；以结点以结点v v为终点引入的边的条数，称为该结点为终点引入的边的条数，称为该结点的入度的入度, ,记为记为degdeg- -(v)(v)

23、；而结点的引出度数和引而结点的引出度数和引入度数之和称为该结点的度数，记为入度数之和称为该结点的度数，记为deg(v)deg(v)，即即deg(v)deg(v)degdeg+ +(v)+deg(v)+deg- -(v)(v)；2022-5-42022-5-4计算机科学与工程学院计算机科学与工程学院2222结点的度数结点的度数 在无向图G中，与结点v(vV)关联的边的条数（有环时计算两次），称为该结点的度数，记为deg(v)；最大点度和最小点度分别记为和。在在有向图有向图G GVE中，以结点中，以结点v v为始点引出的为始点引出的边的条数，称为该结点的边的条数，称为该结点的出度出度, ,记为记为

24、degdeg+ +(v)(v)；以结点以结点v v为终点引入的边的条数，称为该结点为终点引入的边的条数，称为该结点的的入度入度, ,记为记为degdeg- -(v)(v)；而结点的引出度数和引而结点的引出度数和引入度数之和称为该结点的入度数之和称为该结点的度数度数，记为，记为deg(v)deg(v)，即即deg(v)deg(v)degdeg+ +(v)+deg(v)+deg- -(v)(v)；2022-5-42022-5-4计算机科学与工程学院计算机科学与工程学院2323对于图对于图G GVE，度数为度数为0 0的结点称为的结点称为孤立结孤立结点点；只由只由孤立结点构成的图孤立结点构成的图G=

25、G=（V V，）称为称为零图；零图；只由一个只由一个孤立结点构成的图称为孤立结点构成的图称为平凡图；平凡图；在图在图G GVE中，称度数为奇数的结点为奇中，称度数为奇数的结点为奇度数结点，度数为偶数的结点为偶度数结点。度数结点，度数为偶数的结点为偶度数结点。3)3) 各点度数相等的图称为正则图，特别将点度为各点度数相等的图称为正则图，特别将点度为k的正则图称为的正则图称为k度正则图。度正则图。2022-5-42022-5-4计算机科学与工程学院计算机科学与工程学院2424对于图对于图G GVE，度数为度数为0 0的结点称为孤立结的结点称为孤立结点；只由孤立结点构成的图点；只由孤立结点构成的图G

26、=G=（V V，）称为称为零图；只由一个孤立结点构成的图称为平凡图；零图；只由一个孤立结点构成的图称为平凡图；在图在图G GVE中，称度数为奇数的结点为中，称度数为奇数的结点为奇奇度数结点度数结点，度数为偶数的结点为，度数为偶数的结点为偶度数结点偶度数结点。3)3) 各点度数相等的图称为正则图，特别将点度为各点度数相等的图称为正则图，特别将点度为k的正则图称为的正则图称为k度正则图。度正则图。2022-5-42022-5-4计算机科学与工程学院计算机科学与工程学院2525对于图对于图G GVE，度数为度数为0 0的结点称为孤立结的结点称为孤立结点；只由孤立结点构成的图点；只由孤立结点构成的图G

27、=G=（V V，）称为称为零图；只由一个孤立结点构成的图称为平凡图；零图；只由一个孤立结点构成的图称为平凡图；在图在图G GVE中，称度数为奇数的结点为奇中，称度数为奇数的结点为奇度数结点，度数为偶数的结点为偶度数结点。度数结点，度数为偶数的结点为偶度数结点。3)3) 各点度数相等的图称为各点度数相等的图称为正则图正则图，特别将点度为，特别将点度为k的正则图称为的正则图称为k度正则图度正则图。2022-5-42022-5-4计算机科学与工程学院计算机科学与工程学院2626例例10.110.1deg(v1)3，deg+(v1)2，degdeg- -(v1)1；deg(vdeg(v2 2) )3

28、3，degdeg+ +(v(v2 2) )2 2，degdeg- -(v(v2 2) )1 1；deg(vdeg(v3 3) )5 5，degdeg+ +(v(v3 3) )2 2，degdeg- -(v(v3 3) )3 3；deg(vdeg(v4 4) )1 1，degdeg+ +(v(v4 4) )0 0，degdeg- -(v(v4 4) )1 1；deg(vdeg(v5 5) )degdeg+ +(v(v5 5) )degdeg- -(v(v5 5) )0 0；v v3 3v v2 2v v1 1v v5 5v v4 42022-5-42022-5-4计算机科学与工程学院计算机科学与

29、工程学院2727例例10.110.1deg(v1)3，deg+(v1)2，deg-(v1)1；deg(vdeg(v2 2) )3 3，degdeg+ +(v(v2 2) )2 2，degdeg- -(v(v2 2) )1 1；deg(vdeg(v3 3) )5 5，degdeg+ +(v(v3 3) )2 2，degdeg- -(v(v3 3) )3 3；deg(vdeg(v4 4) )1 1，degdeg+ +(v(v4 4) )0 0，degdeg- -(v(v4 4) )1 1；deg(vdeg(v5 5) )degdeg+ +(v(v5 5) )degdeg- -(v(v5 5) )0

30、 0；v v3 3v v2 2v v1 1v v5 5v v4 42022-5-42022-5-4计算机科学与工程学院计算机科学与工程学院2828例例10.110.1deg(v1)3，deg+(v1)2，deg-(v1)1；deg(v2)3，deg+(v2)2，deg-(v2)1；deg(vdeg(v3 3) )5 5，degdeg+ +(v(v3 3) )2 2，degdeg- -(v(v3 3) )3 3；deg(vdeg(v4 4) )1 1，degdeg+ +(v(v4 4) )0 0，degdeg- -(v(v4 4) )1 1；deg(vdeg(v5 5) )degdeg+ +(v

31、(v5 5) )degdeg- -(v(v5 5) )0 0；v v3 3v v2 2v v1 1v v5 5v v4 42022-5-42022-5-4计算机科学与工程学院计算机科学与工程学院2929例例10.110.1deg(v1)3，deg+(v1)2，deg-(v1)1；deg(v2)3，deg+(v2)2，deg-(v2)1；deg(v3)5，deg+(v3)2，deg-(v3)3；deg(vdeg(v4 4) )1 1，degdeg+ +(v(v4 4) )0 0，degdeg- -(v(v4 4) )1 1；deg(vdeg(v5 5) )degdeg+ +(v(v5 5) )d

32、egdeg- -(v(v5 5) )0 0；v v3 3v v2 2v v1 1v v5 5v v4 42022-5-42022-5-4计算机科学与工程学院计算机科学与工程学院3030例例10.110.1deg(v1)3，deg+(v1)2，deg-(v1)1；deg(v2)3，deg+(v2)2，deg-(v2)1；deg(v3)5，deg+(v3)2，deg-(v3)3；deg(v4)1，deg+(v4)0，deg-(v4)1；deg(vdeg(v5 5) )degdeg+ +(v(v5 5) )degdeg- -(v(v5 5) )0 0；v v3 3v v2 2v v1 1v v5 5

33、v v4 42022-5-42022-5-4计算机科学与工程学院计算机科学与工程学院3131握手定理（握手定理（Euler,1736Euler,1736年）年）n 定理定理10.110.1（握手定理）（握手定理）对于任何（对于任何（n,mn,m）图）图G =G =（V V，E E），所有结点的度数的总和等于边数的两倍，即：），所有结点的度数的总和等于边数的两倍，即： 证明：证明：根据结点度数的定义，在计算结点度数时每条根据结点度数的定义，在计算结点度数时每条边对于它所关联的结点被计算了两次，因此，边对于它所关联的结点被计算了两次，因此，G G中结中结点度数的总和恰好为边数点度数的总和恰好为边数

34、m m的的2 2倍。倍。deg( )2v Vvm；2022-5-42022-5-4计算机科学与工程学院计算机科学与工程学院3232推论推论10.1.1 在图在图G GVE中，其中，其V Vvv1 1,v,v2 2,v,v3 3, ,v,vn n ，E Eee1 1，e e2 2，e em m ，度数为奇数的结点个数为偶数。，度数为奇数的结点个数为偶数。证明证明设设V V1 1v|vv|v V V且且deg(v)deg(v)奇数奇数 ，V V2 2v|vv|v V V且且deg(v)deg(v)偶数偶数 。显然，。显然，V V1 1VV2 2，且，且V V1 1VV2 2V V，于是，于是有：有

35、：12deg( )deg( )deg( )2v Vv Vv Vvvvm。由于上式中的由于上式中的2m2m和和|V|V2 2|(|(偶数之和为偶数偶数之和为偶数) )均为偶数，因均为偶数，因而也为偶数。于是而也为偶数。于是|V|V1 1| |为偶数为偶数( (因为因为V V1 1中的结点中的结点v v之之deg(v)deg(v)都为奇数都为奇数) )，即奇度数的结点个数为偶数。，即奇度数的结点个数为偶数。2022-5-42022-5-4计算机科学与工程学院计算机科学与工程学院3333推论推论10.1.1 在图在图G GVE中，其中，其V Vvv1 1,v,v2 2,v,v3 3, ,v,vn n

36、 ，E Eee1 1，e e2 2，e em m ，度数为奇数的结点个数为偶数。，度数为奇数的结点个数为偶数。证明证明 设设V V1 1v|vv|v V V且且deg(v)deg(v)奇数奇数 ，V V2 2v|vv|v V V且且deg(v)deg(v)偶数偶数 。显然，。显然，V V1 1VV2 2，且，且V V1 1VV2 2V V，于是，于是有：有：12deg( )deg( )deg( )2v Vv Vv Vvvvm。由于上式中的由于上式中的2m2m和和|V|V2 2|(|(偶数之和为偶数偶数之和为偶数) )均为偶数，因均为偶数，因而也为偶数。于是而也为偶数。于是|V|V1 1| |为

37、偶数为偶数( (因为因为V V1 1中的结点中的结点v v之之deg(v)deg(v)都为奇数都为奇数) )，即奇度数的结点个数为偶数。，即奇度数的结点个数为偶数。2022-5-42022-5-4计算机科学与工程学院计算机科学与工程学院3434推论推论10.1.1 在图在图G GVE中，其中，其V Vvv1 1,v,v2 2,v,v3 3, ,v,vn n ，E Eee1 1，e e2 2，e em m ，度数为奇数的结点个数为偶数。，度数为奇数的结点个数为偶数。证明证明 设设V V1 1v|vv|v V V且且deg(v)deg(v)奇数奇数 ，V V2 2v|vv|v V V且且deg(v

38、)deg(v)偶数偶数 。显然，。显然，V V1 1VV2 2，且，且V V1 1VV2 2V V，于是，于是有：有：21deg(deg( )deg(2)v Vv Vv Vmvvv。由于上式中的由于上式中的2m2m和和|V|V2 2|(|(偶数之和为偶数偶数之和为偶数) )均为偶数，因均为偶数，因而也为偶数。于是而也为偶数。于是|V|V1 1| |为偶数为偶数( (因为因为V V1 1中的结点中的结点v v之之deg(v)deg(v)都为奇数都为奇数) )，即奇度数的结点个数为偶数。，即奇度数的结点个数为偶数。2022-5-42022-5-4计算机科学与工程学院计算机科学与工程学院3535de

39、g ( )deg ( )v Vv Vvvm，n 定理定理10.210.2：对于任何（对于任何（n,mn,m）有向图）有向图G =G =（V V，E E），则），则所有结点的引出度数之和等于所有结点的引入度数之所有结点的引出度数之和等于所有结点的引入度数之和，所有结点的度数的总和等于边数的两倍，即：和，所有结点的度数的总和等于边数的两倍，即：deg( )deg ( )deg ( )2v Vv Vv Vvvvm。证明：（略）。证明：（略）。2022-5-42022-5-4计算机科学与工程学院计算机科学与工程学院3636度数序列度数序列n 设设V Vvv1 1, v, v2 2,v,vn n 为图为

40、图G G的结点集，称的结点集，称(deg(v(deg(v1 1),deg(v),deg(v2 2),deg(v),deg(vn n)为为G G的的度数序列度数序列。上图的度数序列为（上图的度数序列为（3,3,5,1,03,3,5,1,0）。）。v v3 3v v2 2v v1 1v v5 5v v4 42022-5-42022-5-4计算机科学与工程学院计算机科学与工程学院3737度数序列度数序列n 设Vv1, v2,vn为图G的结点集，称(deg(v1),deg(v2),deg(vn)为G的度数序列。上图的度数序列为（上图的度数序列为（3,3,5,1,03,3,5,1,0）。）。v v3 3

41、v v2 2v v1 1v v5 5v v4 42022-5-42022-5-4计算机科学与工程学院计算机科学与工程学院3838子图子图 n定义定义10.410.4 设有图设有图G GV 和图和图H HV 。若若V V2 2 V V1 1，E E2 2 E E1 1，则称，则称H H是是G G的的子图子图，记为记为H H G G。即即V V2 2 V V1 1或或E E2 2 E E1 1，则称，则称H H是是G G的的真子图真子图，记为记为H H G G。若若V V2 2=V=V1 1，则称，则称H H是是G G的生成子图的生成子图。设设V V2 2= =V V1 1且且E E2 2=E=E

42、1 1或或E E2 2= =，则称，则称H H是是G G的平凡子图。的平凡子图。1)1) 设设v是图是图G G的一个结点，从的一个结点，从G G中删去结点中删去结点v及其关联的全及其关联的全部边后得到的图称为部边后得到的图称为G G的删点子图，简记为的删点子图，简记为G Gv。2022-5-42022-5-4计算机科学与工程学院计算机科学与工程学院3939子图子图 n定义定义10.410.4 设有图设有图G GV 和图和图H HV 。若V2V1，E2E1，则称H是G的子图，记为HG。即V2V1或E2E1，则称H是G的真子图，记为HG。若若V V2 2=V=V1 1，则称，则称H H是是G G的

43、的生成子图生成子图。设设V V2 2= =V V1 1且且E E2 2=E=E1 1或或E E2 2= =，则称，则称H H是是G G的的平凡子图平凡子图。设设v是图是图G G的一个结点，从的一个结点，从G G中删去结点中删去结点v及其关联的全及其关联的全部边后得到的图称为部边后得到的图称为G G的删点子图，简记为的删点子图，简记为G Gv。2022-5-42022-5-4计算机科学与工程学院计算机科学与工程学院4040子图子图 n定义定义10.410.4 设有图设有图G GV 和图和图H HV 。若V2V1，E2E1，则称H是G的子图，记为HG。即V2V1或E2E1，则称H是G的真子图，记为

44、HG。若V2=V1，则称H是G的生成子图。设V2=V1且E2=E1或E2=，则称H是G的平凡子图。设设v是图是图G G的一个结点，从的一个结点，从G G中删去结点中删去结点v及其关联的全及其关联的全部边后得到的图称为部边后得到的图称为G G的的删点子图，删点子图，简记为简记为G Gv。2022-5-42022-5-4计算机科学与工程学院计算机科学与工程学院4141设设e e是图是图G G的一条边，从的一条边，从G G中删去边中删去边e e后得到的图称为后得到的图称为G G删边子图，删边子图，简记为简记为G Ge e。图图G GVE ，S S V V，则，则G(S)=(SG(S)=(S，E E)

45、 )是一个以是一个以S S为为结点，以结点，以E E=uv|u,vuv|u,v S,uvS,uv E E 为边集的图，称为边集的图，称为为G G的点诱导子图的点诱导子图。图图G GVE ， T T E E且且T T，则，则G G（T T）是一个以）是一个以T T为为边集，以边集，以T T中各边关联的全部结点为结点集的图，称中各边关联的全部结点为结点集的图，称为为G G的边诱导子图。的边诱导子图。 2022-5-42022-5-4计算机科学与工程学院计算机科学与工程学院4242设e是图G的一条边，从G中删去边e后得到的图称为G删边子图，简记为Ge。图图G GVE ，S S V V，则，则G(S)

46、=(SG(S)=(S，E E) )是一个以是一个以S S为为结点，以结点，以E E=uv|u,vuv|u,v S,uvS,uv E E 为边集的图，称为边集的图，称为为G G的的点诱导子图点诱导子图。图图G GVE ， T T E E且且T T，则，则G G（T T）是一个以）是一个以T T为为边集，以边集，以T T中各边关联的全部结点为结点集的图，称中各边关联的全部结点为结点集的图，称为为G G的边诱导子图。的边诱导子图。 2022-5-42022-5-4计算机科学与工程学院计算机科学与工程学院4343设e是图G的一条边，从G中删去边e后得到的图称为G删边子图，简记为Ge。图G ，SV，则G

47、(S)=(S，E)是一个以S为结点，以E=uv|u,vS,uvE为边集的图，称为G的点诱导子图。图图G GVE ， T T E E且且T T，则，则G G（T T）是一个以）是一个以T T为为边集，以边集，以T T中各边关联的全部结点为结点集的图，称中各边关联的全部结点为结点集的图，称为为G G的的边诱导子图边诱导子图。 2022-5-42022-5-4计算机科学与工程学院计算机科学与工程学院4444G G1 1v vG G1 1-V-VG G2 2e e1 1e e2 2G G2 2-e-e1 1,e,e2 2 e e3 3e e2 2e e1 1v v2 2v v1 1G G3 3e e3

48、 3e e2 2e e1 1v v2 2v v1 1删点子图删点子图删边子图删边子图点诱导子图点诱导子图G3(v1,v2)边诱导子图边诱导子图G3(e1,e2,e3)例例10.210.22022-5-42022-5-4计算机科学与工程学院计算机科学与工程学院4545G G1 1v vG G1 1-V-VG G2 2e e1 1e e2 2G G2 2-e-e1 1,e,e2 2 e e3 3e e2 2e e1 1v v2 2v v1 1G G3 3e e3 3e e2 2e e1 1v v2 2v v1 1删点子图删点子图删边子图删边子图点诱导子图点诱导子图G3(v1,v2)边诱导子图边诱导

49、子图G3(e1,e2,e3)例例10.210.22022-5-42022-5-4计算机科学与工程学院计算机科学与工程学院4646完全图完全图设设G G为一个具有为一个具有n n个结点的无向简单个结点的无向简单图，如果图，如果G G中任一个结点都与其余中任一个结点都与其余n-1n-1个结点个结点相邻接，则称相邻接，则称G G为为无向完全图无向完全图，简称，简称G G为为完全完全图图，记为记为K Kn n。设设G G为一个具有为一个具有n n个结点的有向简单个结点的有向简单图，若对于任意图，若对于任意u,vu,v V(uV(u v)v)，既有有向边既有有向边，又有有向边又有有向边，则称则称G G为

50、有向完为有向完全图，在不发生误解的情况下，也记为全图，在不发生误解的情况下，也记为K Kn n。无向完全图无向完全图K Kn n的边数为的边数为= =n(n-1)n(n-1)，有向，有向完全图完全图K Kn n的边数为的边数为= n(n-1)= n(n-1)。 2nP2nC122022-5-42022-5-4计算机科学与工程学院计算机科学与工程学院4747完全图完全图设G为一个具有n个结点的无向简单图，如果G中任一个结点都与其余n-1个结点相邻接，则称G为无向完全图，简称G为完全图，记为Kn。设设G G为一个具有为一个具有n n个结点的有向简单个结点的有向简单图，若对于任意图，若对于任意u,v

51、u,v V(uV(u v)v)，既有有向边既有有向边，又有有向边又有有向边，则称则称G G为为有向完有向完全图全图，在不发生误解的情况下，也记为，在不发生误解的情况下，也记为K Kn n。无向完全图无向完全图K Kn n的边数为的边数为= =n(n-1)n(n-1)，有向，有向完全图完全图K Kn n的边数为的边数为= n(n-1)= n(n-1)。 2nP2nC122022-5-42022-5-4计算机科学与工程学院计算机科学与工程学院4848完全图完全图设G为一个具有n个结点的无向简单图，如果G中任一个结点都与其余n-1个结点相邻接，则称G为无向完全图，简称G为完全图，记为Kn。设G为一个

52、具有n个结点的有向简单图，若对于任意u,vV(uv)，既有有向边，又有有向边，则称G为有向完全图，在不发生误解的情况下，也记为Kn。无向完全图无向完全图K Kn n的的边数边数为为= =n(n-1)n(n-1)，有向，有向完全图完全图K Kn n的的边数边数为为= n(n-1)= n(n-1)。 2nP2nC122022-5-42022-5-4计算机科学与工程学院计算机科学与工程学院4949补图补图n 设设G GVE为具有为具有n n个结点的简单图个结点的简单图, ,从完全图从完全图K Kn n中中删去删去G G中的所有边而得到中的所有边而得到的图称为的图称为G G相对于完全图相对于完全图K

53、Kn n的补图的补图，简，简称称G G的的补图补图，记为记为 。n 这里，当这里，当G G为有向图时，则为有向图时，则K Kn n为有向完为有向完全图；当全图；当G G为无向图时，则为无向图时，则K Kn n为无向完为无向完全图。全图。n 显然，显然，G G与与 互为补图，即互为补图，即 。 GGGG2022-5-42022-5-4计算机科学与工程学院计算机科学与工程学院5050补图补图n 设G为具有n个结点的简单图,从完全图Kn中删去G中的所有边而得到的图称为G相对于完全图Kn的补图，简称G的补图，记为 。n 这里，当这里，当G G为有向图时，则为有向图时，则K Kn n为有向完为有向完全图

54、；当全图；当G G为无向图时，则为无向图时，则K Kn n为无向完为无向完全图。全图。n 显然，显然，G G与与 互为补图，即互为补图，即 。 GGGG2022-5-42022-5-4计算机科学与工程学院计算机科学与工程学院5151例例10.310.32022-5-42022-5-4计算机科学与工程学院计算机科学与工程学院5252二部图二部图 设图设图G=G=，如果它的结点集可以划分，如果它的结点集可以划分成两个子集成两个子集X X和和Y Y，使得它的，使得它的每一条边的一个关每一条边的一个关联结点在联结点在X X中，另一个关联结点在中，另一个关联结点在Y Y中中，则这样，则这样的图称为的图称

55、为二部图二部图。 设设|X|=n|X|=n1 1，|Y|=n|Y|=n2 2。如果。如果X X中的每一个结点中的每一个结点与与Y Y中的全部结点都邻接，则称中的全部结点都邻接，则称G G为完全二部图，为完全二部图，并记为并记为K Kn1,n2n1,n2。2022-5-42022-5-4计算机科学与工程学院计算机科学与工程学院5353二部图二部图 设图G=，如果它的结点集可以划分成两个子集X和Y，使得它的每一条边的一个关联结点在X中，另一个关联结点在Y中，则这样的图称为二部图。 设设|X|=n|X|=n1 1，|Y|=n|Y|=n2 2。如果如果X X中的每一个结点中的每一个结点与与Y Y中的全

56、部结点都邻接中的全部结点都邻接，则称，则称G G为为完全二部图完全二部图，并记为并记为K Kn1,n2n1,n2。2022-5-42022-5-4计算机科学与工程学院计算机科学与工程学院5454图的同构图的同构a ab bc cd da ab bc cd da ab bc cd da ab bc cd d2022-5-42022-5-4计算机科学与工程学院计算机科学与工程学院5555定义定义10-1.610-1.6n 设两个图设两个图G=G=和和G=G=，如果，如果存在存在双射函数双射函数g g：VVVV，使得对于任意的，使得对于任意的e=(ve=(vi i,v,vj j) ) （ 或 者（

57、或 者 v ） E E 当 且 仅 当当 且 仅 当 e e (g(v(g(vi i),g(v),g(vj j) （或者（或者g(v)）E，则则称称G G与与G G同构同构，记为，记为GGGG。（同构是指两个图的边1-1对应）n 图的同构关系是图集上的等价关系。图的同构关系是图集上的等价关系。 2022-5-42022-5-4计算机科学与工程学院计算机科学与工程学院5656定义定义10-1.610-1.6n 设两个图G=和G=，如果存在双射函数g：VV，使得对于任意的e=(vi,vj) （或者）E当且仅当e(g(vi),g(vj) （或者）E，则称G与G同构，记为GG。（同构是指两个图的边1-

58、1对应）n 图的同构关系是图集上的等价关系。图的同构关系是图集上的等价关系。 2022-5-42022-5-4计算机科学与工程学院计算机科学与工程学院5757例例10.410.4G1 G2：av1，bv2，cv3，dv4，ev5a ab bd dc ce ev v4 4v v1 1v v3 3v v2 2v v5 5G G1 1G G2 2a ab bd dc ce eG G3 3G G4 4v v4 4v v1 1v v3 3v v2 2v v5 5G G3 3GG4 4：avav1 1，bvbv4 4，cvcv2 2，dvdv5 5，evev3 3；2022-5-42022-5-4计算机科

59、学与工程学院计算机科学与工程学院5858例例10.510.5G5 G6：av1，bv2，cv3，dv4，ev7，fv6，gv9，hv8，iv5，jv10a ab bd dc ce ef fg gj jh hi iG G5 5G G6 6v v8 8v v1 1v v1010v v2 2v v7 7v v3 3v v4 4v v5 5v v6 6v v9 9彼得森图彼得森图2022-5-42022-5-4计算机科学与工程学院计算机科学与工程学院5959两个图同构的必要条件两个图同构的必要条件 结点数目相同结点数目相同； 边数相同边数相同； 度数相同的结点数相同。度数相同的结点数相同。注意：这三个

60、条件并不是充分条件。例如下面两注意：这三个条件并不是充分条件。例如下面两个图满足这三个条件，但它们不同构。个图满足这三个条件，但它们不同构。2022-5-42022-5-4计算机科学与工程学院计算机科学与工程学院6060两个图同构的必要条件两个图同构的必要条件 结点数目相同； 边数相同； 度数相同的结点数相同。注意注意：这三个条件并不是充分条件。例如下面两：这三个条件并不是充分条件。例如下面两个图满足这三个条件，但它们不同构。个图满足这三个条件，但它们不同构。y yx xu uv vx xy yv vu u2022-5-42022-5-4计算机科学与工程学院计算机科学与工程学院6161两个图同构的必要条件两个图同构