离散数学(第10.1)陈瑜

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

2、 ，（a,b ） 称为无序对 。与序偶不同，无论a,b是否相等，均有： (a,b)(b,a)。 8/6/20224计算机科学与工程学院图的定义定义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 。 8/6/20225计算机科学与工程学院图的定义定义1

3、0-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 。8/6/20226计算机科学与工程学院图的定义定义10-1.1一个图是一个序偶，记为 G，其中： 1）V（G）v1,v2,v3,vn是一个有限的非空集合，vi(i1,2,3,n)称为结点,简称点，V为结

4、点集； 2）E（G）e1,e2,e3,em是一个有限的集合，ei(i1,2,3,m)称为边，E为边集，E中的每个元素都是由V中不同结点所构成的无序对，且不含重复元素。 3）图G的结点数称为G的阶，用n表示，G的边数用m表示，也可表示成(G)=m 。 8/6/20227计算机科学与工程学院图的分类(按边的方向)若边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)。8/6/20228计算机科学与工程学院图的分类(按边的方向)若边e与无序结点对(u，v)相对应，则称边e为无向边,记为e(u，v)，这时称u，v是边e的两个端点；若边e与有序结点对相对应，则称边e为有向边，记为e，这时称u是边e的始点。v是边e的终点，统称为e的端点；e是u的出边，是v的入边。每条边都是无向边的图称为无向图；每条边都是有向边的图称为有向图；有些边是无向边，而另一些是有向边的图称为混合图。用小圆圈表示V中的结点，用由u指向v的有向线段表示，无向线段表

6、示(u,v)。8/6/20229计算机科学与工程学院图的分类(按边的方向)若边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)。8/6/202210计算机科学与工程学院图的分类(按边的方向)若边e与无序结点对(u，v)相对应，则称边

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

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

9、个结点、m条边的图称为(n，m)图；e1e2e5v3v2v1e3e4e6v5v48/6/202213计算机科学与工程学院几个概念在一个图中，关联结点vi和vj的边e，无论是有向的还是无向的，均称边e与结点vI和vj相关联，而vi和vj称为邻接点，否则称为不邻接的；关联于同一个结点的两条边称为邻接边；图中关联同一个结点的边称为环(或自回路)；图中不与任何结点相邻接的结点称为孤立结点；仅由孤立结点组成的图称为零图；仅含一个结点的零图称为平凡图；含有n个结点、m条边的图称为(n，m)图；e1e2e5v3v2v1e3e4e6v5v48/6/202214计算机科学与工程学院图的分类(按边的重数)在有向图

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

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

12、(按权)赋权图G是一个三重组，其中V是结点集合，E是边的集合，g是边E上的权值。非赋权图称为无权图。v3v2v1v456678795G18/6/202218计算机科学与工程学院结点的度数 在无向图G中，与结点v(vV)关联的边的条数（有环时计算两次），称为该结点的度数，记为deg(v)；最大点度和最小点度分别记为和。在有向图G中，以结点v为始点引出的边的条数，称为该结点的出度,记为deg+(v)；以结点v为终点引入的边的条数，称为该结点的入度,记为deg-(v)；而结点的引出度数和引入度数之和称为该结点的度数，记为deg(v)，即deg(v)deg+(v)+deg-(v)；8/6/202219

13、计算机科学与工程学院结点的度数 在无向图G中，与结点v(vV)关联的边的条数（有环时计算两次），称为该结点的度数，记为deg(v)；最大点度和最小点度分别记为和。在有向图G中，以结点v为始点引出的边的条数，称为该结点的出度,记为deg+(v)；以结点v为终点引入的边的条数，称为该结点的入度,记为deg-(v)；而结点的引出度数和引入度数之和称为该结点的度数，记为deg(v)，即deg(v)deg+(v)+deg-(v)；8/6/202220计算机科学与工程学院对于图G，度数为0的结点称为孤立结点；只由孤立结点构成的图G=（V，）称为零图；只由一个孤立结点构成的图称为平凡图；在图G中，称度数为奇

14、数的结点为奇度数结点，度数为偶数的结点为偶度数结点。各点度数相等的图称为正则图，特别将点度为k的正则图称为k度正则图。8/6/202221计算机科学与工程学院对于图G，度数为0的结点称为孤立结点；只由孤立结点构成的图G=（V，）称为零图；只由一个孤立结点构成的图称为平凡图；在图G中，称度数为奇数的结点为奇度数结点，度数为偶数的结点为偶度数结点。各点度数相等的图称为正则图，特别将点度为k的正则图称为k度正则图。8/6/202222计算机科学与工程学院对于图G，度数为0的结点称为孤立结点；只由孤立结点构成的图G=（V，）称为零图；只由一个孤立结点构成的图称为平凡图；在图G中，称度数为奇数的结点为奇

15、度数结点，度数为偶数的结点为偶度数结点。各点度数相等的图称为正则图，特别将点度为k的正则图称为k度正则图。8/6/202223计算机科学与工程学院例10.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(v5)deg+(v5)deg-(v5)0；v3v2v1v5v48/6/202224计算机科学与工程学院例10.1deg(v1)3，deg+(v1)2，deg-(v1)1；deg(v2)3，deg+(v2)

16、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；v3v2v1v5v48/6/202225计算机科学与工程学院例10.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(v5)deg+(v5)deg-(v5)0；v3v2v1v5v48/6/202226计算机科学与工程学

17、院例10.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(v5)deg+(v5)deg-(v5)0；v3v2v1v5v48/6/202227计算机科学与工程学院例10.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；de

18、g(v5)deg+(v5)deg-(v5)0；v3v2v1v5v48/6/202228计算机科学与工程学院握手定理（Euler,1736年）定理10-1.1（握手定理）对于任何（n,m）图G =（V，E），所有结点的度数的总和等于边数的两倍，即： 证明：根据结点度数的定义，在计算结点度数时每条边对于它所关联的结点被计算了两次，因此，G中结点度数的总和恰好为边数m的2倍。8/6/202229计算机科学与工程学院推论10-1.1.1在图G中，其Vv1,v2,v3,vn，Ee1，e2，em，度数为奇数的结点个数为偶数。证明设V1v|vV且deg(v)奇数，V2v|vV且deg(v)偶数。显然，V1V

19、2，且V1V2V，于是有：由于上式中的2m和|V2|(偶数之和为偶数)均为偶数，因而也为偶数。于是|V1|为偶数(因为V1中的结点v之deg(v)都为奇数)，即奇度数的结点个数为偶数。8/6/202230计算机科学与工程学院推论10-1.1.1在图G中，其Vv1,v2,v3,vn，Ee1，e2，em，度数为奇数的结点个数为偶数。证明设V1v|vV且deg(v)奇数，V2v|vV且deg(v)偶数。显然，V1V2，且V1V2V，于是有：由于上式中的2m和|V2|(偶数之和为偶数)均为偶数，因而也为偶数。于是|V1|为偶数(因为V1中的结点v之deg(v)都为奇数)，即奇度数的结点个数为偶数。8/

20、6/202231计算机科学与工程学院推论10-1.1.1在图G中，其Vv1,v2,v3,vn，Ee1，e2，em，度数为奇数的结点个数为偶数。证明设V1v|vV且deg(v)奇数，V2v|vV且deg(v)偶数。显然，V1V2，且V1V2V，于是有：由于上式中的2m和|V2|(偶数之和为偶数)均为偶数，因而也为偶数。于是|V1|为偶数(因为V1中的结点v之deg(v)都为奇数)，即奇度数的结点个数为偶数。8/6/202232计算机科学与工程学院定理10-1.2：对于任何（n,m）有向图G =（V，E），则所有结点的引出度数之和等于所有结点的引入度数之和，所有结点的度数的总和等于边数的两倍，即：

21、证明：（略）。8/6/202233计算机科学与工程学院度数序列设Vv1, v2,vn为图G的结点集，称(deg(v1),deg(v2),deg(vn)为G的度数序列。上图的度数序列为（3,3,5,1,0）。v3v2v1v5v48/6/202234计算机科学与工程学院度数序列设Vv1, v2,vn为图G的结点集，称(deg(v1),deg(v2),deg(vn)为G的度数序列。上图的度数序列为（3,3,5,1,0）。v3v2v1v5v48/6/202235计算机科学与工程学院子图 定义10-1.4 设有图G和图H。若V2V1，E2E1，则称H是G的子图，记为HG。即V2V1或E2E1，则称H是G

22、的真子图，记为HG。若V2=V1，则称H是G的生成子图。设V2=V1且E2=E1或E2=，则称H是G的平凡子图。设v是图G的一个结点，从G中删去结点v及其关联的全部边后得到的图称为G的删点子图，简记为Gv。8/6/202236计算机科学与工程学院子图 定义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。8/6/202237计算机

23、科学与工程学院子图 定义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。8/6/202238计算机科学与工程学院设e是图G的一条边，从G中删去边e后得到的图称为G删边子图，简记为Ge。图G ，SV，则G(S)=(S，E)是一个以S为结点，以E=uv|u,vS,uvE为边集的图，称为G的点诱导子图。图G ， TE且T，则G（T）是

24、一个以T为边集，以T中各边关联的全部结点为结点集的图，称为G的边诱导子图。 8/6/202239计算机科学与工程学院设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的边诱导子图。 8/6/202240计算机科学与工程学院设e是图G的一条边，从G中删去边e后得到的图称为G删边子图，简记为Ge。图G ，SV，则G(S)=(S，E)是一个以S为结点，以E=uv|u,vS,u

25、vE为边集的图，称为G的点诱导子图。图G ， TE且T，则G（T）是一个以T为边集，以T中各边关联的全部结点为结点集的图，称为G的边诱导子图。 8/6/202241计算机科学与工程学院G1vG1-VG2e1e2G2-e1,e2e3e2e1v2v1G3e3e2e1v2v1删点子图删边子图点诱导子图G3(v1,v2)边诱导子图G3(e1,e2,e3)例10.28/6/202242计算机科学与工程学院G1vG1-VG2e1e2G2-e1,e2e3e2e1v2v1G3e3e2e1v2v1删点子图删边子图点诱导子图G3(v1,v2)边诱导子图G3(e1,e2,e3)例10.28/6/202243计算机科

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

27、v)，既有有向边，又有有向边，则称G为有向完全图，在不发生误解的情况下，也记为Kn。无向完全图Kn的边数为=n(n-1)，有向完全图Kn的边数为= n(n-1)。 8/6/202245计算机科学与工程学院完全图设G为一个具有n个结点的无向简单图，如果G中任一个结点都与其余n-1个结点相邻接，则称G为无向完全图，简称G为完全图，记为Kn。设G为一个具有n个结点的有向简单图，若对于任意u,vV(uv)，既有有向边，又有有向边，则称G为有向完全图，在不发生误解的情况下，也记为Kn。无向完全图Kn的边数为=n(n-1)，有向完全图Kn的边数为= n(n-1)。 8/6/202246计算机科学与工程学院

28、补图设G为具有n个结点的简单图,从完全图Kn中删去G中的所有边而得到的图称为G相对于完全图Kn的补图，简称G的补图，记为 。这里，当G为有向图时，则Kn为有向完全图；当G为无向图时，则Kn为无向完全图。 显然，G与 互为补图，即 。 8/6/202247计算机科学与工程学院补图设G为具有n个结点的简单图,从完全图Kn中删去G中的所有边而得到的图称为G相对于完全图Kn的补图，简称G的补图，记为 。这里，当G为有向图时，则Kn为有向完全图；当G为无向图时，则Kn为无向完全图。 显然，G与 互为补图，即 。 8/6/202248计算机科学与工程学院例10.38/6/202249计算机科学与工程学院二

29、部图 设图G=，如果它的结点集可以划分成两个子集X和Y，使得它的每一条边的一个关联结点在X中，另一个关联结点在Y中，则这样的图称为二部图。 设|X|=n1，|Y|=n2。如果X中的每一个结点与Y中的全部结点都邻接，则称G为完全二部图，并记为Kn1,n2。8/6/202250计算机科学与工程学院二部图 设图G=，如果它的结点集可以划分成两个子集X和Y，使得它的每一条边的一个关联结点在X中，另一个关联结点在Y中，则这样的图称为二部图。 设|X|=n1，|Y|=n2。如果X中的每一个结点与Y中的全部结点都邻接，则称G为完全二部图，并记为Kn1,n2。8/6/202251计算机科学与工程学院图的同构abcdabcdabcdabcd8/6/202252计算机科学与工程学院定义10-1.6设两个图G=和G=，如果存在双射函数g：VV，使得对于任意的e=(vi,vj) （或者）E当且仅当e(g(vi),g(vj) （或者）E，则称G与G同构，记为GG。（同构是指两个图的边1-1对应）图的同构关系是图集上的等价关系。 8/6/202253计算机科