离散数学教案课件.ppt

《离散数学教案课件.ppt》由会员分享，可在线阅读，更多相关《离散数学教案课件.ppt（89页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第8章章图的基本概念图的基本概念本章内容本章内容8.1 图8.2 通路与回路8.3 图的连通性8.4 图的矩阵表示8.5 图的运算基本要求作业8.1 图的基本概念图的基本概念 图的定义 图的一些概念和规定 简单图和多重图 顶点的度数与握手定理 图的同构 完全图与正则图 子图与补图无序积与多重集合无序积与多重集合 设A，B为任意的两个集合，称a,b|aAbB为A与B的无序积，记作A&B。可将无序积中的无序对a,b记为(a,b)，并且允许ab。无论a,b是否相等，均有(a,b)(b,a)，因而A&BB&A。 元素可以重复出现的集合称为多重集合或者多重集，某元素重复出现的次数称为该元素的重复度。定

2、义8.1 一个无向图是一个有序的二元组,记作G，其中（1）V称为顶点集，其元素称为顶点或结点。（2）E称为边集，它是无序积V&V的多重子集，其元素称为无向边，简称边。定义8.2 一个有向图是一个有序的二元组，记作D，其中（1）V称为顶点集，其元素称为顶点或结点。（2）E为边集，它是笛卡儿积VV的多重子集，其元素称为有向边，简称边。无向图和有向图例例8.1 例8.1 (1) 给定无向图G G，其中 V Vvv1 1,v,v2 2,v,v3 3,v,v4 4,v,v5 5 , ,E=(vE=(v1 1,v,v1 1),(v),(v1 1,v,v2 2),(v),(v2 2,v,v3 3),(v),

3、(v2 2,v,v3 3),),(v(v2 2,v,v5 5),(v),(v1 1,v,v5 5),(v),(v4 4,v,v5 5). ). (2) 给定有向图D=D=，其中 V Va,b,c,da,b,c,d ，E E,。 画出G与D的图形。图的一些概念和规定 G表示无向图，但有时用G泛指图(无向的或有向的)。 D只能表示有向图。 V(G)，E(G)分别表示G的顶点集和边集。 若|V(G)|n，则称G为n阶图。 若|V(G)|与|E(G)|均为有限数，则称G为有限图。 若边集E(G)，则称G为零图，此时，又若G为n阶图，则称G为n阶零图，记作Nn，特别地，称N1为平凡图。 在图的定义中规定

4、顶点集V为非空集，但在图的运算中可能产生顶点集为空集的运算结果，为此规定顶点集为空集的图为空图，并将空图记为。 图的一些概念和规定图的一些概念和规定标定图与非标定图、基图标定图与非标定图、基图 将图的集合定义转化成图形表示之后，常用ek表示无向边(vi,vj)（或有向边），并称顶点或边用字母标定的图为标定图，否则称为非标定图。 将有向图各有向边均改成无向边后的无向图称为原来图的基图。 易知标定图与非标定图是可以相互转化的，任何无向图G的各边均加上箭头就可以得到以G为基图的有向图。 关联与关联次数关联与关联次数 设G为无向图，ek(vi,vj)E，称vi,vj为ek的端点，ek与vi或ek与vj

5、是彼此相关联的。若vivj，则称ek与vi或ek与vj的关联次数为1。若vivj，则称ek与vi的关联次数为2，并称ek为环。任意的vlV，若vlvi且vlvj，则称ek与vl的关联次数为0。环、孤立点环、孤立点 设D为有向图，ekE，称vi,vj为ek的端点。若vivj，则称ek为D中的环。 无论在无向图中还是在有向图中，无边关联的顶点均称为孤立点。 相邻相邻 设无向图G，vi，vjV，ek，elE。若etE，使得et(vi，vj)，则称vi与vj是相邻的。若ek与el至少有一个公共端点，则称ek与el是相邻的。 若ek的终点为el的始点，则称ek与el相邻。邻接邻接 设有向图D，vi，vj

6、V，ek，elE。若etE，使得et，则称vi为et的始点，vj为et的终点，并称vi邻接到vj，vj邻接于vi。邻域邻域 设无向图G，vV，称u|uV(u,v)Euv为v的邻域，记做NG(v)。称NG(v)v为v的闭邻域，记做NG(v)。称e|eEe与v相关联为v的关联集，记做IG(v)。邻域邻域 设有向图D，vV，称u|uVEuv为v的后继元集，记做+D(v)。称u|uVEuv为v的先驱元集，记做-D(v)。称+D(v)-D(v)为v的邻域，记做ND(v)。称ND(v)v为v的闭邻域，记做ND(v)。简单图与多重图简单图与多重图 定义8.3 在无向图中，关联一对顶点的无向边如果多于1条，则

7、称这些边为平行边，平行边的条数称为重数。在有向图中，关联一对顶点的有向边如果多于1条，并且这些边的始点和终点相同(也就是它们的方向相同)，则称这些边为平行边。含平行边的图称为多重图。既不含平行边也不含环的图称为简单图。顶点的度数定义8.4 设G为一无向图，vV，称v作为边的端点次数之和为v的度数，简称为度，记做 dG(v)。在不发生混淆时，简记为d(v)。出度、入度出度、入度设D为有向图，vV，称v作为边的始点次数之和为v的出度，记做d+D(v)，简记作d+(v)。称v作为边的终点次数之和为v的入度，记做d -D(v)，简记作d-(v)。称d+(v)+d-(v)为v的度数，记做d(v)。图的度

8、数的相关概念图的度数的相关概念 在无向图G中，最大度 (G)maxd(v)|vV(G)最小度 (G)mind(v)|vV(G) 图的度数的相关概念图的度数的相关概念 在有向图D中，最大出度+(D)maxd+(v)|vV(D)最小出度+(D)mind+(v)|vV(D)最大入度-(D)maxd-(v)|vV(D)最小入度-(D)mind-(v)|vV(D) 称度数为1的顶点为悬挂顶点，与它关联的边称为悬挂边。度为偶数(奇数)的顶点称为偶度(奇度)顶点。 握手定理握手定理定理8.1 设G为任意无向图，Vv1,v2,vn，|E|m，则n n12)(iimvd定理8.2 设D D为任意有向图，V V

9、v1 1, ,v2 2, , ,vn ，|E|E|m，则 n nn nn n111)()(,2)(iiiiiimvdvdmvd且握手定理的推论握手定理的推论推论 任何图(无向的或有向的)中，奇度顶点的个数是偶数。问题研究问题研究问题：在一个部门的25个人中间，由于意见不同，是否可能每个人恰好与其他5个人意见一致？解答：不可能。考虑一个图，其中顶点代表人，如果两个人意见相同，可用边连接，所以每个顶点都是奇数度。存在奇数个度数为奇数的图，这是不可能的。度数列度数列设G为一个n阶无向图，Vv1,v2,vn，称d(v1)，d(v2)，d(vn)为G的度数列。对于顶点标定的无向图，它的度数列是唯一的。反

10、之，对于给定的非负整数列dd1,d2,dn，若存在Vv1,v2,vn为顶点集的n阶无向图G，使得d(vi)di，则称d是可图化的。特别地，若所得图是简单图，则称d是可简单图化的。类似地，设D为一个n阶有向图，Vv1,v2,vn，称d(v1)，d(v2)，d(vn)为D的度数列，另外称d+(v1)，d+(v2)，d+(vn)与d-(v1)，d-(v2)，d-(vn)分别为D的出度列和入度列。度数列举例按顶点的标定顺序，度数列为4,4,2,1,3。按字母顺序，度数列，出度列，入度列分别为5,3,3,35,3,3,34,0,2,14,0,2,11,3,1,21,3,1,2可图化的充要条件可图化的充要

11、条件定理8.3 设非负整数列d(d1，d2，dn)，则d是可图化的当且仅当 n n1)2(mod0iid证明 必要性。由握手定理显然得证。充分性。由已知条件可知，d中有偶数个奇数度点。奇数度点两两之间连一边，剩余度用环来实现。5331定理定理8.48.4定理8.4 设G为任意n阶无向简单图，则(G)n-1。 证明 因为G既无平行边也无环，所以G中任何顶点v至多与其余的n-1个顶点均相邻，于是d(v)n-1，由于v的任意性，所以(G)n-1。图的同构图的同构定义8.5 设G1，G2为两个无向图，若存在双射函数f：V1V2，对于vi, ,vjV V1 1，( (vi, ,vj) )E E1 1当且

12、仅当( (f(f(vi),f(),f(vj)E E2 2，并且( (vi, ,vj) )与与( (f(f(vi),f(),f(vj)的重数相同，则称G G1 1与G G2 2是同构的，记做G G1 1G G2 2。说明说明(1) 类似地，可以定义两个有向图的同构。(2) 图的同构关系看成全体图集合上的二元关系。(3) 图的同构关系是等价关系。(4) 在图同构的意义下，图的数学定义与图形表示是一一对应的。 图的同构举例图的同构举例彼得森彼得森( (Petersen) )图图完全图完全图定义8.6 设G为n阶无向简单图，若G中每个顶点均与其余的n-1个顶点相邻，则称G为n阶无向完全图，简称n阶完全

13、图，记做Kn(n1)。 设D为n阶有向简单图，若D中每个顶点都邻接到其余的n-1个顶点，又邻接于其余的n-1个顶点，则称D是n阶有向完全图。设D为n阶有向简单图，若D的基图为n阶无向完全图Kn，则称D是n阶竞赛图。完全图举例完全图举例n阶无向完全图的边数为：n(n-1)/2n阶有向完全图的边数为：n(n-1)n阶竞赛图的边数为： n(n-1)/2K5 53 3阶有向完全图阶有向完全图4 4阶竞赛图阶竞赛图正则图正则图定义8.7 设G为n阶无向简单图，若vV(G)，均有d(v)k，则称G为k-正则图。 举例 n阶零图是0-正则图n阶无向完全图是(n-1)-正则图彼得森图是3-正则图说明 n阶k-

14、正则图中，边数mkn/2。当k为奇数时，n必为偶数。子图子图定义8.8 设G，G为两个图(同为无向图或同为有向图)，若V V且E E，则称G是G的子图，G为G 的母图，记作G G。若V V或E E，则称G 为G的真子图。若V V，则称G 为G的生成子图。 导出子图导出子图 设G为一图，V1V且V1，称以V1为顶点集，以G中两个端点都在V1中的边组成边集E1的图为G的V1导出的子图，记作GV1。设E1E且E1，称以E1为边集，以E1中边关联的顶点为顶点集V1的图为G的E1导出的子图，记作GE1。导出子图举例导出子图举例在上图中，设G为(1)中图所表示，取V1a,b,c，则V1的导出子图GV1为(

15、2)中图所示。取E1e1,e3，则E1的导出子图GE1为(3)中图所示。例例8.38.3(1) 画出4阶3条边的所有非同构的无向简单图。由握手定理可知，所画的无向简单图各顶点度数之和为236，最大度小于或等于3。于是所求无向简单图的度数列应满足的条件是，将6分成4个非负整数，每个整数均大于或等于0且小于或等于3，并且奇数的个数为偶数。将这样的整数列排出来只有下面三种情况：定义定义8.98.9定义8.9 设G为n阶无向简单图，以V为顶点集，以所有使G成为完全图Kn的添加边组成的集合为边集的图，称为G的补图，记作G。若图G G，则称为G是自补图。(1)为自补图(2)和(3)互为补图定义定义8.10

16、8.10定义8.10 设G为无向图。(1)设eE，用G-e表示从G中去掉边e，称为删除e。设E E，用G-E 表示从G中删除E 中所有的边，称为删除E 。(2)设vV，用G-v表示从G中去掉v及所关联的一切边，称为删除顶点v。设V V，用G-V 表示从G中删除V 中所有顶点，称为删除V 。定义定义8.108.10(3)设边e(u,v)E，用Ge表示从G中删除e后，将e的两个端点u,v用一个新的顶点w(或用u或v充当w)代替，使w关联除e外u,v关联的所有边，称为边e的收缩。(4)设u,vV(u,v可能相邻，也可能不相邻)，用G(u,v)(或G+(u,v)表示在u,v之间加一条边(u,v)，称为

17、加新边。举例举例GGe5G e1, , e4 Gv5G v4, , v5 G e58.2 8.2 通路与回路通路与回路定义8.11 设G为无向标定图，G中顶点与边的交替序列vi0ej1vi1ej2vi2ejivil称为vi0到vil的通路，其中，vir-1,vir为ejr的端点，r 1，2，l，vi0，vil分别称为的始点与终点，中边的条数称为它的长度。若vi0vil，则称通路为回路。若的所有边各异，则称为简单通路，又若vi0vil，则称为简单回路。若的所有顶点(除vi0与vij可能相同外)各异，所有边也各异，则称为初级通路或路径，又若vi0vil，则称为初级回路或圈。将长度为奇数的圈称为奇圈

18、，长度为偶数的圈称为偶圈。 关于通路与回路的说明关于通路与回路的说明 在初级通路与初级回路的定义中，仍将初级回路看成初级通路(路径)的特殊情况，只是在应用中初级通路(路径)都是始点与终点不相同的，长为1的圈只能由环生成，长为2的圈只能由平行边生成，因而在简单无向图中，圈的长度至少为3。 若中有边重复出现，则称为复杂通路，又若vi0vil，则称为复杂回路。 在有向图中，通路、回路及分类的定义与无向图中非常相似，只是要注意有向边方向的一致性。 在以上的定义中，将回路定义成通路的特殊情况，即回路也是通路，又初级通路(回路)是简单通路(回路)，但反之不真。通路和回路的简单表示法通路和回路的简单表示法(

19、1)只用边的序列表示通路(回路)。定义8.11中的可以表示成ej1 ,ej2 , ,ejl。(2)在简单图中也可以只用顶点序列表示通路(回路)。定义中的也可以表示vi0 ,vi2 , ,vil。通路和回路的简单表示法通路和回路的简单表示法(3)为了写出非标定图中的通路(回路)，可以先将非标定图标成标定图，再写出通路与回路。(4)在非简单标定图中，当只用顶点序列表示不出某些通路(回路)时，可在顶点序列中加入一些边(这些边是平行边或环)，可称这种表示法为混合表示法。 定理定理8.58.5定理8.5 在n阶图G中，若从顶点vi到vj（vivj）存在通路，则从vi到vj存在长度小于或等于n-1的通路。

20、定理定理8.68.6推论 在n阶图G中，若从顶点vi到vj（vivj）存在通路，则vi到vj一定存在长度小于或等于n-1的初级通路（路径）。 定理8.6 在一个n阶图G中，若存在vi 到自身的回路，则一定存在vi 到自身长度小于或等于n的回路。 推论 在一个n阶图G中，若存在vi 到自身的简单回路，则一定存在vi 到自身长度小于或等于n的初级回路。8.3 8.3 图的连通性图的连通性 无向图的连通性 无向图中顶点之间的短程线及距离 无向图的连通程度：点割集、割点、边割集、割边、连通度 有向图的连通性及判别方法 扩大路径法与极大路径 二部图及其判别方法 无向图的连通性无向图的连通性定义8.12

21、设无向图G，u,vV，若u,v之间存在通路，则称u,v是连通的，记作uv。 vV，规定vv。 无向图中顶点之间的连通关系 （u,v）| u,vV且u与v之间有通路是自反的、对称的、传递的，因而是V上的等价关系。连通图与连通分支连通图与连通分支定义8.13 若无向图G是平凡图或G中任何两个顶点都是连通的，则称G为连通图，否则称G是非连通图或分离图。说明：完全图Kn(n1)都是连通图零图Nn(n2)都是分离图。 等价类等价类定义8.14 设无向图G，V关于顶点之间的连通关系的商集V/V1,V2,Vk，Vi为等价类，称导出子图GVi(i1,2,k)为G的连通分支，连通分支数k常记为p(G)。 说明

22、若G为连通图，则p(G)1。若G为非连通图，则p(G)2。在所有的n阶无向图中，n阶零图是连通分支最多的，p(Nn)n。 无向图中顶点之间的短程线及距离无向图中顶点之间的短程线及距离 定义8.15 设u,v为无向图G中任意两个顶点，若uv，称u,v之间长度最短的通路为u,v之间的短程线，短程线的长度称为u,v之间的距离，记作d(u,v)。当u,v不连通时，规定d(u,v)。 距离的性质距离的性质距离有以下性质：(1)d(u,v)0，uv时，等号成立。(2)具有对称性，d(u,v)d(v,u)。(3)满足三角不等式： u,v,wV(G)，则d(u,v)+d(v,w)d(u,w)说明：在完全图Kn

23、(n2)中，任何两个顶点之间的距离都是1。在n阶零图Nn(n2)中，任何两个顶点之间的距离都为。无向图的点割集无向图的点割集定义8.16 设无向图G，若存在V V，且V ，使得p(G-V )p(G)，而对于任意的V V ，均有p(G-V )p(G)，则称V 是G的点割集。若V 是单元集，即V v，则称v为割点。 v2 2, ,v4 4, v3 3, v5 5 都是点割集v3 3, ,v5 5都是割点v1 1与v6 6不在任何割集中。 无向图的边割集无向图的边割集定义8.17 设无向图G，若存在E E，且E ，使得p(G-E )p(G)，而对于任意的E E，均有p(G-E )p(G)，则称E是G

24、的边割集，或简称为割集。若E 是单元集，即E e，则称e为割边或桥。 e6 6,e,e5 5,e2 2, ,e3 3,e1 1, ,e2 2, e3 3, ,e4 4,e1 1, ,e4 4,e1 1, ,e3 3,e2 2, ,e4 4 都是割集，e6 6, ,e5 5是桥。 点连通度点连通度定义8.18 设G为无向连通图且为非完全图，则称 K(G)min|V |V 为G的点割集为G的点连通度，简称连通度。说明说明说明 连通度是为了产生一个不连通图需要删去的点的最少数目。规定完全图Kn(n1)的点连通度为n-1，规定非连通图的点连通度为0，若K(G)k，则称G是k-连通图，k为非负整数。说明

25、 K(G)有时简记为K。上例中图的点连通度为1，此图为1-连通图。K5的点连通度K4，所以K5是1-连通图，2-连通图，3-连通图，4-连通图。若G是k-连通图（k1）则在G中删除任何k-1个顶点后，所得图一定还是连通的。 边连通度边连通度定义8.19 设G是无向连通图，称 (G )min|E | E 是G的点割集为G的边连通度。规定非连通图的边连通度为0。若(G)r，则称G是r 边-连通图。 说明说明说明 (G)也可以简记为。若G是 r 边-连通图，则在G中任意删除r-1条边后，所得图依然是连通的。完全图Kn的边连通度为n-1，因而Kn是r边-连通图，0rn-1。例例8.68.6求所示各图的

26、点连通度，边连通度，并指出它们各是几连通图及几边连通图。最后将它们按点连通程度及边连通程度排序。K4 4K3 3K2 2K1 1K=1,1,=2 2K2 2K0 0K0 0例例8.68.6的解答的解答设第i个图的点连通度为Ki，边连通度为i， i 1,2,8。容易看出，K114，K223，K332，K441， K5=1 5=2，K662，K770，K880。(1)是k-连通图，k边-连通图，k1,2,3,4。(2)是k-连通图，k边-连通图，k1,2,3。(3)是k-连通图，k边-连通图，k1,2。(4)是1-连通图，1边-连通图。(5)是1-连通图，k边-连通图，k1,2。(6)是k-连通图

27、，k边-连通图，k1,2。(7)是0-连通图，0边-连通图。(8)是0-连通图，0边-连通图。点连通程度为(1)(2)(3)(6)(4)(5)(7)(8)。边连通程度为(1)(2)(3)(5)(6)(4)(7)(8)。定理定理8.78.7定理8.7 对于任何无向图G，有 K(G)(G)(G)例8.7 (1)给出一些无向简单图，使得 K。 (2)给出一些无向简单图，使得 K。解答 (1) n阶无向完全图Kn和n阶零图Nn都满足要求。(2)在两个Kn(n4)之间放置一个顶点v，使v与两个Kn中的每一个的任意两个不同的顶点相邻，所得简单图满足要求。因为这样的图中有一个割点，所以点连通度为1，又因为无

28、桥，而有两条边组成的边割集，所以边连通度为2，当n4时，3，当n5时，4。有向图的连通性有向图的连通性定义8.20 设D为一个有向图。vi,vjV，若从vi到vj存在通路，则称vi可达vj，记作vivj，规定vi总是可达自身的，即vivi。若vivj且vjvi，则称vi与vj是相互可达的，记作vi vj。规定vivi。说明 与都是V上的二元关系，并且不难看出是V上的等价关系。 定义8.21 设D为有向图，vi,vjV，若vivj，称vi到vj长度最短的通路为vi到vj的短程线，短程线的长度为vi到vj的距离，记作d 。说明 与无向图中顶点vi与vj之间的距离d(vi,vj)相比，d除无对称性外

29、，具有d(vi,vj)所具有的一切性质。 连通图连通图定义8.22 设D为一个有向图。若D的基图是连通图，则称D是弱连通图，简称为连通图。若vi,vjV，vivj与vjvi至少成立其一，则称D是单向连通图。若均有vi vj，则称D是强连通图。说明 强连通图一定是单向连通图，单向连通图一定是弱连通图。 强连通图与单向连通图的判定定理强连通图与单向连通图的判定定理定理8.8 设有向图D，Vv1,v2,vn。D是强连通图当且仅当D中存在经过每个顶点至少一次的回路。 定理8.9 设D是n阶有向图，D是单向连通图当且仅当D中存在经过每个顶点至少一次的通路。扩大路径法扩大路径法 设G为n阶无向图，E，设l

30、为G中一条路径，若此路径的始点或终点与通路外的顶点相邻，就将它们扩到通路中来。继续这一过程，直到最后得到的通路的两个端点不与通路外的顶点相邻为止。设最后得到的路径为l+k(长度为l的路径扩大成了长度为l+k的路径)，称l+k为“极大路径”，称使用此种方法证明问题的方法为“扩大路径法”。关于极大路径的说明关于极大路径的说明 由某条路经扩大出的极大路径不唯一。 极大路径不一定是图中最长的路径。二部图二部图定义8.23 设G为一个无向图，若能将V分成V1和V2(V1V2V,V1V2)，使得G中的每条边的两个端点都是一个属于V1，另一个属于V2，则称G为二部图（或称二分图，偶图等），称V1和V2为互补

31、顶点子集。常将二部图G记为。若G是简单二部图，V1中每个顶点均与V2中所有顶点相邻，则称G为完全二部图，记为Kr,s，其中r|V1|，s|V2|。 说明 n阶零图为二部图。 二部图的判定定理二部图的判定定理定理8.10 一个无向图G是二部图当且仅当G中无奇数长度的回路。证明 必要性。若G中无回路，结论显然成立。若G中有回路，只需证明G中无奇圈。设C为G中任意一圈，令Cvi1vi2vilvi1，易知 l2。不妨设vi1V1，则必有vilV-V1=V2，而l必为偶数，于是C为偶圈，由C的任意性可知结论成立。二部图的判定定理二部图的判定定理充分性。不妨设G为连通图，否则可对每个连通分支进行讨论。设v

32、0为G中任意一个顶点，令V1v|vV(G)d(v0,v)为偶数V2v|vV(G)d(v0,v)为奇数易知，V1,V2,V1V2，V1V2V(G)。二部图的判定定理二部图的判定定理下面只要证明V1中任意两顶点不相邻,V2中任意两点也不相邻。若存在vi,vjV1相邻，令(vi,vj)e，设v0到vi,vj的短程线分别为i,j，则它们的长度d(v0,vi),d(v0,vj)都是偶数，于是ije中一定含奇圈，这与已知条件矛盾。类似可证，V2中也不存在相邻的顶点，于是G为二部图。8.4 8.4 图的矩阵表示图的矩阵表示定义8.24 设无向图G，Vv1,v2,vn，Ee1,e2,em，令mij为顶点vi与

33、边ej的关联次数，则称(mij)nm为G的关联矩阵，记作M(G)。10000110000011001112M(G)有向图的关联矩阵有向图的关联矩阵定义8.25 设有向图D中无环，Vv1,v2,vn，Ee1,e2,em，令 的终点为不关联为的始点为jijijiijevevevm101则称( (mij) )nm为D的关联矩阵，记作M( (D) )。1-1-1-00110000011-100011-M(D)有向图的邻接矩阵有向图的邻接矩阵定义8.26 设有向图D，Vv1,v2,vn，Ee1,e2,，em，令aij(1)为顶点vi邻接到顶点vj边的条数，称(aij(1)nn为D的邻接矩阵，记作A(D)

34、，或简记为A。1101000100120000A有向图的可达矩阵有向图的可达矩阵定义8.27 设D为有向图。Vv1,v2,vn，令 pij1 vi 可达 vj0 否则称( (pij) )nn为D的可达矩阵，记作P( (D)，简记为P。 1101101111110001P8.5 图的运算图的运算定义8.28 设G1，G2为两个图。若V1V2，则称G1与G2是不交的。若E1E2，则称G1与G2是边不交的或边不重的。 说明：不交的图，必然是边不交的，但反之不真。图的运算图的运算定义8.29 设G1，G2为不含孤立点的两个图（它们同为无向图或同为有向图）。(1)称以E1E2为边集，以E1E2中边关联的

35、顶点组成的集合为顶点集的图为G1与G2的并图，记作G1G2。(2)称以E1-E2为边集，以E1-E2中边关联的顶点组成的集合为顶点集的图为G1与G2的差图，记作G1-G2。 图的运算图的运算(3)称以E1E2为边集，以E1E2中边关联的顶点组成的集合为顶点集的图为G1与G2的交图，记作G1G2。 (4)称以E1 E2为边集（为集合之间的对称差运算），以E1 E2中边关联的顶点组成的集合为顶点集的图为G1与G2的环和，记作G1 G2。 定义8.29的说明(1)若G1G2，则G1G2G1G2G1(G2)G1-G2G2-G1G1 G2这就是在图的定义中给出空图概念的原因。 (2)当G1与G2边不重时

36、，G1G2G1-G2G1G2-G1G2G1G2G1G2 (3)图之间环和的定义也可以用并、交、差给出，即G1 G2(G1G2)-(G1G2)基本要求基本要求 理解与图的定义有关的诸多概念，以及它们之间的相互关系。 深刻理解握手定理及其推论的内容，并能熟练地应用它们。 深刻理解图同构、简单图、完全图、正则图、子图、补图、二部图等概念及其它们的性质和相互关系，并能熟练地应用这些性质和关系。基本要求基本要求 深刻理解通路与回路的定义、相互关系及其分类，掌握通路与回路的各种不同的表示方法。 理解无向图的点连通度、边连通度等概念及其之间的关系，并能熟练地求出给定的较为简单的图的点连通度与边连通度。 理解有向图连通性的概念及其分类，掌握判断有向连通图类型的方法。作业作业习题6、10、19、20、21、29、30、32、33、49