离散数学第101陈瑜演示课件

1、陈瑜,Email：22.12.2020,离散数学,计算机学院,22.12.2020,2,主要内容,图的基本概念 什么是图 图的分类 结点的度数 握手定理 子图与补图 完全图 补图 图的同构,22.12.2020,3,10.1 图的基本概念,无序积的定义：设A,B 为任意集合，称集合A&B (a,b)|aA ，bB为A 与B 的无序积 ，（a,b ） 称为无序对 。 与序偶不同，无论a,b是否相等，均有： (a,b)(b,a)。,22.12.2020,4,10.1 图的基本概念,无序积的定义：设A,B 为任意集合，称集合A&B (a,b)|aA ，bB为A 与B 的无序

2、积 ，（a,b ） 称为无序对 。 与序偶不同，无论a,b是否相等，均有： (a,b)(b,a)。,22.12.2020,5,图的定义,定义10-1.1一个图是一个序偶，记为,G，其中： 1）V（G）v1,v2,v3,vn是一个有限的非空集合，vi(i1,2,3,n)称为结点,简称点，V为结点集； 2）E（G）e1,e2,e3,em是一个有限的集合，ei(i1,2,3,m)称为边，E为边集，E中的每个元素都是由V中不同结点所构成的无序对，且不含重复元素。 3）图G的结点数称为G的阶，用n表示，G的边数用m表示，也可表示成(G)=m 。,22.12.2020,6,图的定义,定义10-1.1一个图

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

4、,e2,e3,em是一个有限的集合，ei(i1,2,3,m)称为边，E为边集，E中的每个元素都是由V中不同结点所构成的无序对，且不含重复元素。 3）图G的结点数称为G的阶，用n表示，G的边数用m表示，也可表示成(G)=m 。,22.12.2020,8,图的分类(按边的方向),若边e与无序结点对(u，v)相对应，则称边e为无向边,记为e(u，v)，这时称u，v是边e的两个端点； 若边e与有序结点对相对应，则称边e为有向边，记为e，这时称u是边e的始点。v是边e的终点，统称为e的端点；e是u的出边，是v的入边。 每条边都是无向边的图称为无向图； 每条边都是有向边的图称为有向图； 有些边是无向边，而

5、另一些是有向边的图称为混合图。,用小圆圈表示V中的结点，用由u指向v的有向线段表示，无向线段表示(u,v)。,22.12.2020,9,图的分类(按边的方向),若边e与无序结点对(u，v)相对应，则称边e为无向边,记为e(u，v)，这时称u，v是边e的两个端点； 若边e与有序结点对相对应，则称边e为有向边，记为e，这时称u是边e的始点。v是边e的终点，统称为e的端点；e是u的出边，是v的入边。 每条边都是无向边的图称为无向图； 每条边都是有向边的图称为有向图； 有些边是无向边，而另一些是有向边的图称为混合图。,用小圆圈表示V中的结点，用由u指向v的有向线段表示，无向线段表示(u,v)。,22.

6、12.2020,10,图的分类(按边的方向),若边e与无序结点对(u，v)相对应，则称边e为无向边,记为e(u，v)，这时称u，v是边e的两个端点； 若边e与有序结点对相对应，则称边e为有向边，记为e，这时称u是边e的始点。v是边e的终点，统称为e的端点；e是u的出边，是v的入边。 每条边都是无向边的图称为无向图； 每条边都是有向边的图称为有向图； 有些边是无向边，而另一些是有向边的图称为混合图。,用小圆圈表示V中的结点，用由u指向v的有向线段表示，无向线段表示(u,v)。,22.12.2020,11,图的分类(按边的方向),若边e与无序结点对(u，v)相对应，则称边e为无向边,记为e(u，v

7、)，这时称u，v是边e的两个端点； 若边e与有序结点对相对应，则称边e为有向边，记为e，这时称u是边e的始点。v是边e的终点，统称为e的端点；e是u的出边，是v的入边。 每条边都是无向边的图称为无向图； 每条边都是有向边的图称为有向图； 有些边是无向边，而另一些是有向边的图称为混合图。,用小圆圈表示V中的结点，用由u指向v的有向线段表示，无向线段表示(u,v)。,22.12.2020,12,几个概念,在一个图中，关联结点vi和vj的边e，无论是有向的还是无向的，均称边e与结点vI和vj相关联，而vi和vj称为邻接点，否则称为不邻接的；,关联于同一个结点的两条边称为邻接边； 图中关联同一个结点的

8、边称为环(或自回路)； 图中不与任何结点相邻接的结点称为孤立结点； 仅由孤立结点组成的图称为零图； 仅含一个结点的零图称为平凡图； 含有n个结点、m条边的图 称为(n，m)图；,22.12.2020,13,几个概念,在一个图中，关联结点vi和vj的边e，无论是有向的还是无向的，均称边e与结点vI和vj相关联，而vi和vj称为邻接点，否则称为不邻接的；,关联于同一个结点的两条边称为邻接边； 图中关联同一个结点的边称为环(或自回路)； 图中不与任何结点相邻接的结点称为孤立结点； 仅由孤立结点组成的图称为零图； 仅含一个结点的零图称为平凡图； 含有n个结点、m条边的图 称为(n，m)图；,22.12

9、.2020,14,几个概念,在一个图中，关联结点vi和vj的边e，无论是有向的还是无向的，均称边e与结点vI和vj相关联，而vi和vj称为邻接点，否则称为不邻接的；,关联于同一个结点的两条边称为邻接边； 图中关联同一个结点的边称为环(或自回路)； 图中不与任何结点相邻接的结点称为孤立结点； 仅由孤立结点组成的图称为零图； 仅含一个结点的零图称为平凡图； 含有n个结点、m条边的图 称为(n，m)图；,22.12.2020,15,图的分类(按边的重数),在有向图中，两个结点间(包括结点自身间)若有同始点和同终点的几条边，则这几条边称为平行边。 在无向图中，两个结点间(包括结点自身间)若有几条边，则

10、这几条边称为平行边； 含有平行边的图称为多重图； 含有环的多重图称为广义图（伪图）； 满足定义9-1.1的图称为简单图。 将多重图和广义图中的平行边代之以一条边，去掉环，可以得到一个简单图，称为原来图的基图。,22.12.2020,16,图的分类(按边的重数),在有向图中，两个结点间(包括结点自身间)若有同始点和同终点的几条边，则这几条边称为平行边。 在无向图中，两个结点间(包括结点自身间)若有几条边，则这几条边称为平行边； 含有平行边的图称为多重图； 含有环的多重图称为广义图（伪图）； 满足定义10-1.1的图称为简单图。 将多重图和广义图中的平行边代之以一条边，去掉环，可以得到一个简单图，

11、称为原来图的基图。,22.12.2020,17,图的分类(按边的重数),在有向图中，两个结点间(包括结点自身间)若有同始点和同终点的几条边，则这几条边称为平行边。 在无向图中，两个结点间(包括结点自身间)若有几条边，则这几条边称为平行边； 含有平行边的图称为多重图； 含有环的多重图称为广义图（伪图）； 满足定义10-1.1的图称为简单图。 将多重图和广义图中的平行边代之以一条边，去掉环，可以得到一个简单图，称为原来图的基图。,22.12.2020,18,图的分类(按权),赋权图G是一个三重组，其中V是结点集合，E是边的集合，g是边E上的权值。非赋权图称为无权图。,v3,v2,v1,v4,G1,

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

13、为和。 在有向图G中，以结点v为始点引出的边的条数，称为该结点的出度,记为deg+(v)；以结点v为终点引入的边的条数，称为该结点的入度,记为deg-(v)；而结点的引出度数和引入度数之和称为该结点的度数，记为deg(v)，即deg(v)deg+(v)+deg-(v)；,22.12.2020,21,对于图G，度数为0的结点称为孤立结点；只由孤立结点构成的图G=（V，）称为零图；只由一个孤立结点构成的图称为平凡图； 在图G中，称度数为奇数的结点为奇度数结点，度数为偶数的结点为偶度数结点。 各点度数相等的图称为正则图，特别将点度为k的正则图称为k度正则图。,22.12.2020,22,对于图G，度

14、数为0的结点称为孤立结点；只由孤立结点构成的图G=（V，）称为零图；只由一个孤立结点构成的图称为平凡图； 在图G中，称度数为奇数的结点为奇度数结点，度数为偶数的结点为偶度数结点。 各点度数相等的图称为正则图，特别将点度为k的正则图称为k度正则图。,22.12.2020,23,对于图G，度数为0的结点称为孤立结点；只由孤立结点构成的图G=（V，）称为零图；只由一个孤立结点构成的图称为平凡图； 在图G中，称度数为奇数的结点为奇度数结点，度数为偶数的结点为偶度数结点。 各点度数相等的图称为正则图，特别将点度为k的正则图称为k度正则图。,22.12.2020,24,例10.1,deg(v1)3，deg

15、+(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(v5)deg+(v5)deg-(v5)0；,22.12.2020,25,例10.1,deg(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(v5)deg+(v5)deg-(v5)0；,

16、22.12.2020,26,例10.1,deg(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(v5)deg+(v5)deg-(v5)0；,22.12.2020,27,例10.1,deg(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-(

17、v4)1； deg(v5)deg+(v5)deg-(v5)0；,22.12.2020,28,例10.1,deg(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(v5)deg+(v5)deg-(v5)0；,22.12.2020,29,握手定理（Euler,1736年）,定理10-1.1（握手定理）对于任何（n,m）图G =（V，E），所有结点的度数的总和等于边数的两倍，即： 证明：根据结点度数的定义，在计算

18、结点度数时每条边对于它所关联的结点被计算了两次，因此，G中结点度数的总和恰好为边数m的2倍。,22.12.2020,30,推论10-1.1.1,在图G中，其Vv1,v2,v3,vn，E,e1，e2，em，度数为奇数的结点个数为偶数。,证明设V1v|vV且deg(v)奇数，V2v|vV且deg(v)偶数。显然，V1V2，且V1V2V，于是有：,由于上式中的2m和|V2|(偶数之和为偶数)均为偶数，因而也为偶数。于是|V1|为偶数(因为V1中的结点v之deg(v)都为奇数)，即奇度数的结点个数为偶数。,22.12.2020,31,推论10-1.1.1,在图G中，其Vv1,v2,v3,vn，E,e1

19、，e2，em，度数为奇数的结点个数为偶数。,证明设V1v|vV且deg(v)奇数，V2v|vV且deg(v)偶数。显然，V1V2，且V1V2V，于是有：,由于上式中的2m和|V2|(偶数之和为偶数)均为偶数，因而也为偶数。于是|V1|为偶数(因为V1中的结点v之deg(v)都为奇数)，即奇度数的结点个数为偶数。,22.12.2020,32,推论10-1.1.1,在图G中，其Vv1,v2,v3,vn，E,e1，e2，em，度数为奇数的结点个数为偶数。,证明设V1v|vV且deg(v)奇数，V2v|vV且deg(v)偶数。显然，V1V2，且V1V2V，于是有：,由于上式中的2m和|V2|(偶数之和

20、为偶数)均为偶数，因而也为偶数。于是|V1|为偶数(因为V1中的结点v之deg(v)都为奇数)，即奇度数的结点个数为偶数。,22.12.2020,33,定理10-1.2：对于任何（n,m）有向图G =（V，E），则所有结点的引出度数之和等于所有结点的引入度数之和，所有结点的度数的总和等于边数的两倍，即：,证明：（略）。,22.12.2020,34,度数序列,设Vv1, v2,vn为图G的结点集，称(deg(v1),deg(v2),deg(vn)为G的度数序列。,上图的度数序列为（3,3,5,1,0）。,22.12.2020,35,度数序列,设Vv1, v2,vn为图G的结点集，称(deg(v1

21、),deg(v2),deg(vn)为G的度数序列。,上图的度数序列为（3,3,5,1,0）。,22.12.2020,36,子图,定义10-1.4 设有图G和图H。 若V2V1，E2E1，则称H是G的子图，记为HG。 即V2V1或E2E1，则称H是G的真子图，记为HG。 若V2=V1，则称H是G的生成子图。 设V2=V1且E2=E1或E2=，则称H是G的平凡子图。 设v是图G的一个结点，从G中删去结点v及其关联的全部边后得到的图称为G的删点子图，简记为Gv。,22.12.2020,37,子图,定义10-1.4 设有图G和图H。 若V2V1，E2E1，则称H是G的子图，记为HG。 即V2V1或E2

22、E1，则称H是G的真子图，记为HG。 若V2=V1，则称H是G的生成子图。 设V2=V1且E2=E1或E2=，则称H是G的平凡子图。 设v是图G的一个结点，从G中删去结点v及其关联的全部边后得到的图称为G的删点子图，简记为Gv。,22.12.2020,38,子图,定义10-1.4 设有图G和图H。 若V2V1，E2E1，则称H是G的子图，记为HG。 即V2V1或E2E1，则称H是G的真子图，记为HG。 若V2=V1，则称H是G的生成子图。 设V2=V1且E2=E1或E2=，则称H是G的平凡子图。 设v是图G的一个结点，从G中删去结点v及其关联的全部边后得到的图称为G的删点子图，简记为Gv。,2

23、2.12.2020,39,设e是图G的一条边，从G中删去边e后得到的图称为G删边子图，简记为Ge。 图G ，SV，则G(S)=(S，E)是一个以S为结点，以E=uv|u,vS,uvE为边集的图，称为G的点诱导子图。 图G ， TE且T，则G（T）是一个以T为边集，以T中各边关联的全部结点为结点集的图，称为G的边诱导子图。,22.12.2020,40,设e是图G的一条边，从G中删去边e后得到的图称为G删边子图，简记为Ge。 图G ，SV，则G(S)=(S，E)是一个以S为结点，以E=uv|u,vS,uvE为边集的图，称为G的点诱导子图。 图G ， TE且T，则G（T）是一个以T为边集，以T中各边

24、关联的全部结点为结点集的图，称为G的边诱导子图。,22.12.2020,41,设e是图G的一条边，从G中删去边e后得到的图称为G删边子图，简记为Ge。 图G ，SV，则G(S)=(S，E)是一个以S为结点，以E=uv|u,vS,uvE为边集的图，称为G的点诱导子图。 图G ， TE且T，则G（T）是一个以T为边集，以T中各边关联的全部结点为结点集的图，称为G的边诱导子图。,22.12.2020,42,G1,v,G1-V,G2,e1,e2,G2-e1,e2,e3,e2,e1,v2,v1,G3,e3,e2,e1,v2,v1,删点子图,删边子图,点诱导子图 G3(v1,v2),边诱导子图 G3(e1

25、,e2,e3),例10.2,22.12.2020,43,G1,v,G1-V,G2,e1,e2,G2-e1,e2,e3,e2,e1,v2,v1,G3,e3,e2,e1,v2,v1,删点子图,删边子图,点诱导子图 G3(v1,v2),边诱导子图 G3(e1,e2,e3),例10.2,22.12.2020,44,完全图,设G为一个具有n个结点的无向简单图，如果G中任一个结点都与其余n-1个结点相邻接，则称G为无向完全图，简称G为完全图，记为Kn。 设G为一个具有n个结点的有向简单图，若对于任意u,vV(uv)，既有有向边，又有有向边，则称G为有向完全图，在不发生误解的情况下，也记为Kn。,无向完全图

26、Kn的边数为=n(n-1)，有向完全图Kn的边数为= n(n-1)。,22.12.2020,45,完全图,设G为一个具有n个结点的无向简单图，如果G中任一个结点都与其余n-1个结点相邻接，则称G为无向完全图，简称G为完全图，记为Kn。 设G为一个具有n个结点的有向简单图，若对于任意u,vV(uv)，既有有向边，又有有向边，则称G为有向完全图，在不发生误解的情况下，也记为Kn。,无向完全图Kn的边数为=n(n-1)，有向完全图Kn的边数为= n(n-1)。,22.12.2020,46,完全图,设G为一个具有n个结点的无向简单图，如果G中任一个结点都与其余n-1个结点相邻接，则称G为无向完全图，简

27、称G为完全图，记为Kn。 设G为一个具有n个结点的有向简单图，若对于任意u,vV(uv)，既有有向边，又有有向边，则称G为有向完全图，在不发生误解的情况下，也记为Kn。,无向完全图Kn的边数为=n(n-1)，有向完全图Kn的边数为= n(n-1)。,22.12.2020,47,补图,设G为具有n个结点的简单图,从完全图Kn中删去G中的所有边而得到的图称为G相对于完全图Kn的补图，简称G的补图，记为 。 这里，当G为有向图时，则Kn为有向完全图；当G为无向图时，则Kn为无向完全图。,显然，G与 互为补图，即 。,22.12.2020,48,补图,设G为具有n个结点的简单图,从完全图Kn中删去G中

28、的所有边而得到的图称为G相对于完全图Kn的补图，简称G的补图，记为 。 这里，当G为有向图时，则Kn为有向完全图；当G为无向图时，则Kn为无向完全图。,显然，G与 互为补图，即 。,22.12.2020,49,例10.3,22.12.2020,50,二部图,设图G=，如果它的结点集可以划分成两个子集X和Y，使得它的每一条边的一个关联结点在X中，另一个关联结点在Y中，则这样的图称为二部图。 设|X|=n1，|Y|=n2。如果X中的每一个结点与Y中的全部结点都邻接，则称G为完全二部图，并记为Kn1,n2。,22.12.2020,51,二部图,设图G=，如果它的结点集可以划分成两个子集X和Y，使得它的每一条边的一个关联结点在X中，另一个关联结点在Y中，则这样的图称为二部图。 设|X|=n1，|Y|=n2。如果X中的每一个结点与Y中的全部结点都邻接，则称G为完全二部图，并记为Kn1,n2。,2