离散数学第陈瑜PPT学习教案

1、会计学1离散数学第陈瑜离散数学第陈瑜2021-10-172/63n 无序积的定义：无序积的定义：设设A,B A,B 为任意集合，称集合为任意集合，称集合A&B A&B (a,b)|aA (a,b)|aA ，bBbB为为A A 与与B B 的的无序无序积积 ，（，（a,b a,b ） 称为称为无序对无序对 。n 与序偶不同，无论与序偶不同，无论a,ba,b是否相等，均有：是否相等，均有： (a,b)(a,b)(b,a)(b,a)。 第1页/共62页2021-10-173/63n 无序积的定义：设A,B 为任意集合，称集合A&B (a,b)|aA ，bB为A 与B 的无序积 ，（a,b ） 称为无

2、序对 。n 与序偶不同，无论与序偶不同，无论a,ba,b是否相等，均有：是否相等，均有： (a,b)(a,b)(b,a)(b,a)。 第2页/共62页2021-10-174/63n定义定义10-1.110-1.1一个一个图图是一个序偶是一个序偶，记为，记为 G G，其中：，其中： 1 1）V V（G G）vv1 1,v,v2 2,v,v3 3, ,v,vn n 是一个有限的非空集合，是一个有限的非空集合，v vi i(i(i1,2,3,1,2,3,n),n)称为称为结点结点, ,简称简称点点，V V为为结点集结点集； 2 2）E E（G G）ee1 1,e,e2 2,e,e3 3, ,e,em

3、 m 是一个有限的集合，是一个有限的集合，e ei i(i(i1,2,3,1,2,3,m),m)称为边，称为边，E E为边集，为边集，E E中的每个元素都是由中的每个元素都是由V V中不同结点所构成的无序对，且不含重复元素。中不同结点所构成的无序对，且不含重复元素。 3 3）图）图G G的结点数称为的结点数称为G G的阶，用的阶，用n n表示，表示，G G的边数用的边数用m m表示，也可表示成表示，也可表示成 (G)=m(G)=m 。 第3页/共62页2021-10-175/63n定义定义10-1.110-1.1一个一个图图是一个序偶是一个序偶，记为，记为 G G，其中：，其中： 1 1）V（

4、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,1,2,3,m),m)称为称为边边，E E为为边集边集，E E中的每个元素都是由中的每个元素都是由V V中不同结点所构成的无序对，且不含重复元素。中不同结点所构成的无序对，且不含重复元素。 3 3）图）图G G的结点数称为的结点数称为G G的阶，用的阶，用n n表示，表示，G G的边数用的边数用m m表示，也可表示成表示，也可表示成 (G)=m

5、(G)=m 。第4页/共62页2021-10-176/63n定义定义10-1.110-1.1一个一个图图是一个序偶是一个序偶，记为，记为 G G，其中：，其中： 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的结点数称为的结点数称为G G的的阶阶，用，用n n表示，表示，G G的边数用的边数用m m表示，也可表示成表示，也可表示成 (G)=m(G

6、)=m 。 第5页/共62页2021-10-177/631)1)若边若边e e与无序结点对与无序结点对(u(u，v)v)相对应，则称边相对应，则称边e e为为无向边无向边, ,记为记为e e(u(u，v)v)，这时称，这时称u u，v v是边是边e e的两个的两个端点端点；2)2)若边若边e e与有序结点对与有序结点对uv相对应，则称边相对应，则称边e e为有向边，记为为有向边，记为e euv，这时称，这时称u u是边是边e e的始点。的始点。v v是边是边e e的终点，统称为的终点，统称为e e的端点；的端点；e e是是u u的出边，是的出边，是v v的入边。的入边。3)3)每条边都是无向边

7、的图称为无向图；每条边都是无向边的图称为无向图；4)4)每条边都是有向边的图称为有向图；每条边都是有向边的图称为有向图；5)5)有些边是无向边，而另一些是有向边的图称为混合图。有些边是无向边，而另一些是有向边的图称为混合图。n用小圆圈表示用小圆圈表示V V中的结点，用由中的结点，用由u u指向指向v v的有向线段表示的有向线段表示，无向线段表示，无向线段表示(u,v)(u,v)。第6页/共62页2021-10-178/631)若边e与无序结点对(u，v)相对应，则称边e为无向边,记为e(u，v)，这时称u，v是边e的两个端点；2)2)若边若边e e与有序结点对与有序结点对uv相对应，则称边相对

8、应，则称边e e为为有向边有向边，记为，记为e euv，这时称，这时称u u是边是边e e的的始点始点。v v是边是边e e的的终点终点，统称为，统称为e e的的端点端点；e e是是u u的出边，是的出边，是v v的入边。的入边。3)3)每条边都是无向边的图称为无向图；每条边都是无向边的图称为无向图；4)4)每条边都是有向边的图称为有向图；每条边都是有向边的图称为有向图；5)5)有些边是无向边，而另一些是有向边的图称为混合图。有些边是无向边，而另一些是有向边的图称为混合图。n用小圆圈表示用小圆圈表示V V中的结点，用由中的结点，用由u u指向指向v v的有向线段表示的有向线段表示，无向线段表示

9、，无向线段表示(u,v)(u,v)。第7页/共62页2021-10-179/631)若边e与无序结点对(u，v)相对应，则称边e为无向边,记为e(u，v)，这时称u，v是边e的两个端点；2)若边e与有序结点对相对应，则称边e为有向边，记为e，这时称u是边e的始点。v是边e的终点，统称为e的端点；e是u的出边，是v的入边。3)3)每条边都是无向边的图称为每条边都是无向边的图称为无向图无向图；4)4)每条边都是有向边的图称为每条边都是有向边的图称为有向图有向图；5)5)有些边是无向边，而另一些是有向边的图称为有些边是无向边，而另一些是有向边的图称为混合图混合图。n用小圆圈表示用小圆圈表示V V中的

10、结点，用由中的结点，用由u u指向指向v v的有向线段表示的有向线段表示，无向线段表示，无向线段表示(u,v)(u,v)。第8页/共62页2021-10-1710/631)若边e与无序结点对(u，v)相对应，则称边e为无向边,记为e(u，v)，这时称u，v是边e的两个端点；2)若边e与有序结点对相对应，则称边e为有向边，记为e，这时称u是边e的始点。v是边e的终点，统称为e的端点；e是u的出边，是v的入边。3)每条边都是无向边的图称为无向图；4)每条边都是有向边的图称为有向图；5)有些边是无向边，而另一些是有向边的图称为混合图。n用用小圆圈小圆圈表示表示V V中的中的结点结点，用由用由u u指

11、向指向v v的的有向线段有向线段表示表示，无向线段无向线段表示表示(u,v)(u,v)。第9页/共62页2021-10-1711/631)1)在一个图中，关联结点在一个图中，关联结点v vi i和和v vj j的边的边e e，无论是有向的还是无向的，均称边，无论是有向的还是无向的，均称边e e与结点与结点v vI I和和v vj j相关联相关联，而，而v vi i和和v vj j称为称为邻接点邻接点，否则称为，否则称为不邻接的不邻接的；2)2)关联于同一个结点的两条边称为邻接边；关联于同一个结点的两条边称为邻接边；3)3)图中关联同一个结点的边称为环图中关联同一个结点的边称为环( (或自回路或

12、自回路) )；4)4)图中不与任何结点相邻接的结点称为孤立结点；图中不与任何结点相邻接的结点称为孤立结点；5)5)仅由孤立结点组成的图称为零图；仅由孤立结点组成的图称为零图；6)6)仅含一个结点的零图称为平凡图；仅含一个结点的零图称为平凡图；7)7)含有含有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 4第10页/共62页2021-10-1712/631)在一个图中，关联结点vi和vj的边e，无论是有向的还是无向的，均称边e与结点vI

13、和vj相关联，而vi和vj称为邻接点，否则称为不邻接的；2)2)关联于同一个结点的两条边称为关联于同一个结点的两条边称为邻接边邻接边；3)3)图中关联同一个结点的边称为图中关联同一个结点的边称为环环( (或或自回路自回路) )；4)4)图中不与任何结点相邻接的结点称为图中不与任何结点相邻接的结点称为孤立结点孤立结点；5)5)仅由孤立结点组成的图称为零图；仅由孤立结点组成的图称为零图；6)6)仅含一个结点的零图称为平凡图；仅含一个结点的零图称为平凡图；7)7)含有含有n n个结点、个结点、m m条边的图条边的图称为称为(n(n，m)m)图；图；e e1 1e e2 2e e5 5v v3 3v

14、v2 2v v1 1e e3 3e e4 4e e6 6v v5 5v v4 4第11页/共62页2021-10-1713/631)在一个图中，关联结点vi和vj的边e，无论是有向的还是无向的，均称边e与结点vI和vj相关联，而vi和vj称为邻接点，否则称为不邻接的；2)关联于同一个结点的两条边称为邻接边；3)图中关联同一个结点的边称为环(或自回路)；4)图中不与任何结点相邻接的结点称为孤立结点；5)5)仅由孤立结点组成的图称为仅由孤立结点组成的图称为零图零图；6)6)仅含一个结点的零图称为仅含一个结点的零图称为平凡图平凡图；7)7)含有含有n n个结点、个结点、m m条边的图条边的图称为称为

15、(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 4第12页/共62页2021-10-1714/631)1)在有向图中，两个结点间在有向图中，两个结点间( (包括结点自身间包括结点自身间) )若有同始点和同终点的几条边，则这几条边称为若有同始点和同终点的几条边，则这几条边称为平行边平行边。2)2)在无向图中，两个结点间在无向图中，两个结点间( (包括结点自身间包括结点自身间) )若有几条边，则这几条边称为若有几条边，则这几条边称为平行边平行边；3)3)含有平行边的图称为多重图；含有平行边的图

16、称为多重图；4)4)含有环的多重图称为广义图（伪图）；含有环的多重图称为广义图（伪图）；5)5)满足定义满足定义9-1.19-1.1的图称为简单图。的图称为简单图。6)6)将多重图和广义图中的平行边代之以一条边，去掉环，可以得到一个简单图，称为原来图的基图。将多重图和广义图中的平行边代之以一条边，去掉环，可以得到一个简单图，称为原来图的基图。第13页/共62页2021-10-1715/631)在有向图中，两个结点间(包括结点自身间)若有同始点和同终点的几条边，则这几条边称为平行边。2)在无向图中，两个结点间(包括结点自身间)若有几条边，则这几条边称为平行边；3)3)含有平行边的图称为含有平行边

17、的图称为多重图多重图；4)4)含有含有环环的多重图称为的多重图称为广义图（伪图）广义图（伪图）；5)5)满足定义满足定义10-1.110-1.1的图称为的图称为简单图简单图。6)6)将多重图和广义图中的平行边代之以一条边，去掉环，可以得到一个简单图，称为原来图的基图。将多重图和广义图中的平行边代之以一条边，去掉环，可以得到一个简单图，称为原来图的基图。第14页/共62页2021-10-1716/631)在有向图中，两个结点间(包括结点自身间)若有同始点和同终点的几条边，则这几条边称为平行边。2)在无向图中，两个结点间(包括结点自身间)若有几条边，则这几条边称为平行边；3)含有平行边的图称为多重

18、图；4)含有环的多重图称为广义图（伪图）；5)满足定义10-1.1的图称为简单图。6)6)将多重图和广义图中的平行边代之以一条边，去掉环，可以得到一个简单图，称为原来图的将多重图和广义图中的平行边代之以一条边，去掉环，可以得到一个简单图，称为原来图的基图。基图。第15页/共62页2021-10-1717/63n赋权图赋权图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 5

19、G G1 1第16页/共62页2021-10-1718/631)1)在在无向图无向图G GVE中，与结点中，与结点v(vv(v V)V)关联的关联的边的条数（有环时计算两次），称为该结点边的条数（有环时计算两次），称为该结点的的度数度数，记为，记为deg(v)deg(v)；最大点度和最小点度；最大点度和最小点度分别记为分别记为 和和 。2)2)在有向图在有向图G GVE中，以结点中，以结点v v为始点引出为始点引出的 边 的 条 数 ， 称 为 该 结 点 的 出 度的 边 的 条 数 ， 称 为 该 结 点 的 出 度 , , 记 为记 为degdeg+ +(v)(v)；以结点；以结点v v

20、为终点引入的边的条数，为终点引入的边的条数，称为该结点的入度称为该结点的入度, ,记为记为degdeg- -(v)(v)；而结点的；而结点的引出度数和引入度数之和称为该结点的度数引出度数和引入度数之和称为该结点的度数，记为，记为deg(v)deg(v)，即，即deg(v)deg(v)degdeg+ +(v)+deg(v)+deg- -(v)(v)；第17页/共62页2021-10-1719/631)在无向图G中，与结点v(vV)关联的边的条数（有环时计算两次），称为该结点的度数，记为deg(v)；最大点度和最小点度分别记为和。2)2)在在有向图有向图G GVE中，以结点中，以结点v v为始点引

21、出为始点引出的 边 的 条 数 ， 称 为 该 结 点 的的 边 的 条 数 ， 称 为 该 结 点 的 出 度出 度 , , 记 为记 为degdeg+ +(v)(v)；以结点；以结点v v为终点引入的边的条数，为终点引入的边的条数，称为该结点的称为该结点的入度入度, ,记为记为degdeg- -(v)(v)；而结点的；而结点的引出度数和引入度数之和称为该结点的引出度数和引入度数之和称为该结点的度数度数，记为，记为deg(v)deg(v)，即，即deg(v)deg(v)degdeg+ +(v)+deg(v)+deg- -(v)(v)；第18页/共62页2021-10-1720/633)3)对

22、于图对于图G GVE，度数为，度数为0 0的结点称为的结点称为孤立孤立结点结点；只由孤立结点构成的图；只由孤立结点构成的图G=G=（V V，）称称为为零图；零图；只由一个孤立结点构成的图称为只由一个孤立结点构成的图称为平平凡图；凡图；4)4)在图在图G GVE中，称度数为奇数的结点为奇中，称度数为奇数的结点为奇度数结点，度数为偶数的结点为偶度数结点度数结点，度数为偶数的结点为偶度数结点。5)5)各点度数相等的图称为正则图，特别将点度各点度数相等的图称为正则图，特别将点度为为k的正则图称为的正则图称为k度正则图。度正则图。第19页/共62页2021-10-1721/633)3)对于图对于图G G

23、VE，度数为，度数为0 0的结点称为孤立的结点称为孤立结点；只由孤立结点构成的图结点；只由孤立结点构成的图G=G=（V V，）称称为零图；只由一个孤立结点构成的图称为平为零图；只由一个孤立结点构成的图称为平凡图；凡图；4)4)在图在图G GVE中，称度数为奇数的结点为中，称度数为奇数的结点为奇奇度数结点度数结点，度数为偶数的结点为，度数为偶数的结点为偶度数结点偶度数结点。5)5)各点度数相等的图称为正则图，特别将点度各点度数相等的图称为正则图，特别将点度为为k的正则图称为的正则图称为k度正则图。度正则图。第20页/共62页2021-10-1722/633)3)对于图对于图G GVE，度数为，度

24、数为0 0的结点称为孤立的结点称为孤立结点；只由孤立结点构成的图结点；只由孤立结点构成的图G=G=（V V，）称称为零图；只由一个孤立结点构成的图称为平为零图；只由一个孤立结点构成的图称为平凡图；凡图；4)4)在图在图G GVE中，称度数为奇数的结点为奇中，称度数为奇数的结点为奇度数结点，度数为偶数的结点为偶度数结点度数结点，度数为偶数的结点为偶度数结点。5)5)各点度数相等的图称为各点度数相等的图称为正则图正则图，特别将点度，特别将点度为为k的正则图称为的正则图称为k度正则图度正则图。第21页/共62页2021-10-1723/63deg(v1)3，deg+(v1)2，degdeg- -(v

25、1)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 0；v v3 3v v2 2v v1 1v v5 5v v4 4第22页/共62页2

26、021-10-1724/63deg(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 0；v

27、 v3 3v v2 2v v1 1v v5 5v v4 4第23页/共62页2021-10-1725/63deg(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(v5 5) )degdeg- -(v(v5 5) )0 0

28、；v v3 3v v2 2v v1 1v v5 5v v4 4第24页/共62页2021-10-1726/63deg(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) )degdeg- -(v(v5 5) )0 0；v v3 3v v2 2v v1 1v v5 5v v4 4第25页

29、/共62页2021-10-1727/63deg(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 5v v4 4第26页/共62页2021-10-1728/63n定理定理10-1.110-1.1（握手定理）（握手定理）对于任何（对于任何（n,mn,m）图）图G =

30、G =（V V，E E），所有结点的度数的总和等于边数的两倍，即：），所有结点的度数的总和等于边数的两倍，即： 证明：证明：根据结点度数的定义，在计算结点度数时每条边对于它所关联的结点被计算了两次，因此，根据结点度数的定义，在计算结点度数时每条边对于它所关联的结点被计算了两次，因此，G G中结点度数的总和恰好为边数中结点度数的总和恰好为边数m m的的2 2倍。倍。deg( )2v Vvm；第27页/共62页2021-10-1729/63在图在图G GVE中，其中，其V Vvv1 1,v,v2 2,v,v3 3, ,v,vn n ，E Eee1 1，e e2 2，e em m ，度数为奇数的结点

31、个数为偶数。，度数为奇数的结点个数为偶数。证明证明设设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| |为偶数为偶数( (因为因为V V1 1中的结点中的结点v v之之deg(

32、v)deg(v)都为奇数都为奇数) )，即奇度数的结点个数为偶数。，即奇度数的结点个数为偶数。第28页/共62页2021-10-1730/63在图在图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，于是有：，于是有：12de

33、g( )deg( )deg( )2v Vv Vv Vvvvm。由于上式中的由于上式中的2m2m和和|V|V2 2|(|(偶数之和为偶数偶数之和为偶数) )均为偶数，因而也为偶数。于是均为偶数，因而也为偶数。于是|V|V1 1| |为偶数为偶数( (因为因为V V1 1中的结点中的结点v v之之deg(v)deg(v)都为奇数都为奇数) )，即奇度数的结点个数为偶数。，即奇度数的结点个数为偶数。第29页/共62页2021-10-1731/63在图在图G GVE中，其中，其V Vvv1 1,v,v2 2,v,v3 3, ,v,vn n ，E Eee1 1，e e2 2，e em m ，度数为奇数的

34、结点个数为偶数。，度数为奇数的结点个数为偶数。证明证明设设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，于是有：，于是有：21deg(deg( )deg(2)v Vv Vv Vmvvv。由于上式中的由于上式中的2m2m和和|V|V2 2|(|(偶数之和为偶数偶数之和为偶数) )均为偶数，因而也为偶数。于是均为偶数，因而也为偶数。于是|V|V1 1| |为偶数为偶数( (因为因为V V1 1中的结点中的结点v v之之deg(v

35、)deg(v)都为奇数都为奇数) )，即奇度数的结点个数为偶数。，即奇度数的结点个数为偶数。第30页/共62页2021-10-1732/63deg ( )deg ( )v Vv Vvvm，n定理定理10-1.210-1.2：对于任何（对于任何（n,mn,m）有向图）有向图G =G =（V V，E E），则所有结点的引出度数之和等于所有结点的引入度数之和，所有结点的度数的总和等于边数的两倍，即：），则所有结点的引出度数之和等于所有结点的引入度数之和，所有结点的度数的总和等于边数的两倍，即：deg( )deg ( )deg ( )2v Vv Vv Vvvvm。证明：（略）。证明：（略）。第31页/

36、共62页2021-10-1733/63n 设设V Vvv1 1, v, v2 2, ,v,vn n 为图为图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 4第32页/共62页2021-10-1734/63n 设Vv1, v2,vn为图G的结点集，称(deg(v1),deg(v2),deg(vn)为G的度数序列。上图的度数序列为（上图的度数序列

37、为（3,3,5,1,03,3,5,1,0）。）。v v3 3v v2 2v v1 1v v5 5v v4 4第33页/共62页2021-10-1735/63n定义定义10-1.410-1.4 设有图设有图G GV 和图和图H HV 。1)1)若若V V2 2 V V1 1，E E2 2 E E1 1，则称，则称H H是是G G的的子图子图，记为，记为H H G G。2)2)即即V V2 2 V V1 1或或E E2 2 E E1 1，则称，则称H H是是G G的的真子图真子图，记为，记为H H G G。3)3)若若V V2 2=V=V1 1，则称，则称H H是是G G的生成子图。的生成子图。4

38、)4)设设V V2 2= =V V1 1且且E E2 2=E=E1 1或或E E2 2= =，则称，则称H H是是G G的平凡子图。的平凡子图。5)5)设设v是图是图G G的一个结点，从的一个结点，从G G中删去结点中删去结点v及其关联的全部边后得到的图称为及其关联的全部边后得到的图称为G G的删点子图，简记为的删点子图，简记为G Gv。第34页/共62页2021-10-1736/63n定义定义10-1.410-1.4 设有图设有图G GV 和图和图H HV 。1)若V2V1，E2E1，则称H是G的子图，记为HG。2)即V2V1或E2E1，则称H是G的真子图，记为HG。3)3)若若V V2 2

39、=V=V1 1，则称，则称H H是是G G的的生成子图生成子图。4)4)设设V V2 2= =V V1 1且且E E2 2=E=E1 1或或E E2 2= =，则称，则称H H是是G G的的平凡子图平凡子图。5)5)设设v是图是图G G的一个结点，从的一个结点，从G G中删去结点中删去结点v及其关联的全部边后得到的图称为及其关联的全部边后得到的图称为G G的删点子图，简记为的删点子图，简记为G Gv。第35页/共62页2021-10-1737/63n定义定义10-1.410-1.4 设有图设有图G GV 和图和图H HV 。1)若V2V1，E2E1，则称H是G的子图，记为HG。2)即V2V1或

40、E2E1，则称H是G的真子图，记为HG。3)若V2=V1，则称H是G的生成子图。4)设V2=V1且E2=E1或E2=，则称H是G的平凡子图。5)5)设设v是图是图G G的一个结点，从的一个结点，从G G中删去结点中删去结点v及其关联的全部边后得到的图称为及其关联的全部边后得到的图称为G G的的删点子图，删点子图，简记为简记为G Gv。第36页/共62页2021-10-1738/636)6)设设e e是图是图G G的一条边，从的一条边，从G G中删去边中删去边e e后得到的图称为后得到的图称为G G删边子图，删边子图，简记为简记为G Ge e。7)7)图图G GVE ，S S V V，则，则G(

41、S)=(SG(S)=(S，E E) )是一个以是一个以S S为结点，以为结点，以E E=uv|u,v=uv|u,v S,uvS,uv EE为边集的图，称为为边集的图，称为G G的点诱导子图。的点诱导子图。8)8)图图G GVE ， T T E E且且T T，则，则G G（T T）是一个以）是一个以T T为边集，以为边集，以T T中各边关联的全部结点为结点集的图，称为中各边关联的全部结点为结点集的图，称为G G的边诱导子图。的边诱导子图。 第37页/共62页2021-10-1739/636)设e是图G的一条边，从G中删去边e后得到的图称为G删边子图，简记为Ge。7)7)图图G GVE ，S S

42、V V，则，则G(S)=(SG(S)=(S，E E) )是一个以是一个以S S为结点，以为结点，以E E=uv|u,v=uv|u,v S,uvS,uv EE为边集的图，称为为边集的图，称为G G的的点诱导子图点诱导子图。8)8)图图G GVE ， T T E E且且T T，则，则G G（T T）是一个以）是一个以T T为边集，以为边集，以T T中各边关联的全部结点为结点集的图，称为中各边关联的全部结点为结点集的图，称为G G的边诱导子图。的边诱导子图。 第38页/共62页2021-10-1740/636)设e是图G的一条边，从G中删去边e后得到的图称为G删边子图，简记为Ge。7)图G ，SV，

43、则G(S)=(S，E)是一个以S为结点，以E=uv|u,vS,uvE为边集的图，称为G的点诱导子图。8)8)图图G GVE ， T T E E且且T T，则，则G G（T T）是一个以）是一个以T T为边集，以为边集，以T T中各边关联的全部结点为结点集的图，称为中各边关联的全部结点为结点集的图，称为G G的的边诱导子图边诱导子图。 第39页/共62页2021-10-1741/63G 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

44、e1 1v v2 2v v1 1删点子图删点子图删边子图删边子图点诱导子图点诱导子图G3(v1,v2)边诱导子图边诱导子图G3(e1,e2,e3)例例10.210.2第40页/共62页2021-10-1742/63G 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)边诱导子图边诱导子图G3(e1,e2,e3)例例10.210.2第4

45、1页/共62页2021-10-1743/631.1.设设G G为一个具有为一个具有n n个结点的无向简单个结点的无向简单图，如果图，如果G G中任一个结点都与其余中任一个结点都与其余n-1n-1个结个结点相邻接，则称点相邻接，则称G G为为无向完全图无向完全图，简称，简称G G为为完全图完全图，记为，记为K Kn n。2.2.设设G G为一个具有为一个具有n n个结点的有向简单个结点的有向简单图，若对于任意图，若对于任意u,vu,v V(uV(u v)v)，既有有向边，既有有向边，又有有向边，又有有向边，则称，则称G G为有向完为有向完全图，在不发生误解的情况下，也记为全图，在不发生误解的情况

46、下，也记为K Kn n。无向完全图无向完全图K Kn n的边数为的边数为= =n(n-1)n(n-1)，有向，有向完全图完全图K Kn n的边数为的边数为= n(n-1)= n(n-1)。 2nP2nC12第42页/共62页2021-10-1744/631.设G为一个具有n个结点的无向简单图，如果G中任一个结点都与其余n-1个结点相邻接，则称G为无向完全图，简称G为完全图，记为Kn。2.2.设设G G为一个具有为一个具有n n个结点的有向简单个结点的有向简单图，若对于任意图，若对于任意u,vu,v V(uV(u v)v)，既有有向边，既有有向边，又有有向边，又有有向边，则称，则称G G为为有向

47、完有向完全图全图，在不发生误解的情况下，也记为，在不发生误解的情况下，也记为K Kn n。无向完全图无向完全图K Kn n的边数为的边数为= =n(n-1)n(n-1)，有向，有向完全图完全图K Kn n的边数为的边数为= n(n-1)= n(n-1)。 2nP2nC12第43页/共62页2021-10-1745/631.设G为一个具有n个结点的无向简单图，如果G中任一个结点都与其余n-1个结点相邻接，则称G为无向完全图，简称G为完全图，记为Kn。2.设G为一个具有n个结点的有向简单图，若对于任意u,vV(uv)，既有有向边，又有有向边，则称G为有向完全图，在不发生误解的情况下，也记为Kn。无

48、向完全图无向完全图K Kn n的的边数边数为为= =n(n-1)n(n-1)，有向，有向完全图完全图K Kn n的的边数边数为为= n(n-1)= n(n-1)。 2nP2nC12第44页/共62页2021-10-1746/63n设设G GVE为具有为具有n n个结点的简单图个结点的简单图, ,从完全图从完全图K Kn n中中删去删去G G中的所有边而得到中的所有边而得到的图称为的图称为G G相对于完全图相对于完全图K Kn n的补图的补图，简，简称称G G的的补图补图，记为记为 。n这里，当这里，当G G为有向图时，则为有向图时，则K Kn n为有向完为有向完全图；当全图；当G G为无向图时

49、，则为无向图时，则K Kn n为无向完为无向完全图。全图。n 显然，显然，G G与与 互为补图，即互为补图，即 。 GGGG第45页/共62页2021-10-1747/63n设G为具有n个结点的简单图,从完全图Kn中删去G中的所有边而得到的图称为G相对于完全图Kn的补图，简称G的补图，记为 。n这里，当这里，当G G为有向图时，则为有向图时，则K Kn n为有向完为有向完全图；当全图；当G G为无向图时，则为无向图时，则K Kn n为无向完为无向完全图。全图。n 显然，显然，G G与与 互为补图，即互为补图，即 。 GGGG第46页/共62页2021-10-1748/63第47页/共62页20

50、21-10-1749/63第48页/共62页2021-10-1750/63第49页/共62页2021-10-1751/63a ab bc cd da ab bc cd da ab bc cd da ab bc cd d第50页/共62页2021-10-1752/63n 设两个图设两个图G=G=和和G G=V= ，如果存在，如果存在双 射 函 数双 射 函 数 g g ： V V V V ， 使 得 对 于 任 意 的， 使 得 对 于 任 意 的e=(ve=(vi i,v,vj j) ) （或者（或者v ）E E当且仅当当且仅当ee(g(v(g(vi i),g(v),g(vj j) （或者（或者g(v)）E，则称则称G G与与G G同构同构，记为，记为GGGG。（同构是指两个图的边1-1对应）n 图的同构关系是图集上的等价关系。图的同构关系是图集上的等价关系。 第51页/共6