《图的基本概念》PPT课件.ppt

资源描述

《《图的基本概念》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《图的基本概念》PPT课件.ppt（81页珍藏版）》请在三一办公上搜索。

1、第14章图的基本概念,离散数学,中国地质大学本科生课程,本章内容,14.1 图14.2 通路与回路14.3 图的连通性14.4 图的矩阵表示14.5 图的运算基本要求作业,14.1 图的基本概念,图的定义图的一些概念和规定简单图和多重图顶点的度数与握手定理图的同构完全图与正则图子图与补图,无序积与多重集合,元素可以重复出现的集合称为多重集合或者多重集，某元素重复出现的次数称为该元素的重复度。例如在多重集合a,a,b,b,b,c,d中，a,b,c,d的重复度分别为2,3,1,1。,定义14.1 一个无向图是一个有序的二元组,记作G，其中（1）V称为顶点集，其元素称为顶点或结点。（2）E

2、称为边集，它是无序积V&V的多重子集，其元素称为无向边，简称边。定义14.2 一个有向图是一个有序的二元组，记作D，其中（1）V称为顶点集，其元素称为顶点或结点。（2）E为边集，它是笛卡儿积VV的多重子集，其元素称为有向边，简称边。,无向图和有向图,说明,可以用图形表示图，即用小圆圈（或实心点）表示顶点，用顶点之间的连线表示无向边，用有方向的连线表示有向边。,例14.1,例14.1(1)给定无向图G，其中 Vv1,v2,v3,v4,v5，E=(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5).(2)给定有向图D=，其中 Va,b,c,

3、d，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为平凡图。在图的定义中规定顶点集V为非空集，但在图的运算中可能产生顶点集为空集的运算结果，为此规定顶点集为空集的图为空图，并将空图记为。,标定图与非标定图、基图,将图的集合定义转化成图形表示之后，常用ek表示无向边(vi,vj)（或有向边），并称顶点或边

4、用字母标定的图为标定图，否则称为非标定图。将有向图各有向边均改成无向边后的无向图称为原来图的基图。易知标定图与非标定图是可以相互转化的，任何无向图G的各边均加上箭头就可以得到以G为基图的有向图。,关联与关联次数、环、孤立点,设G为无向图，ek(vi,vj)E，称vi,vj为ek的端点，ek与vi或ek与vj是彼此相关联的。若vivj，则称ek与vi或ek与vj的关联次数为1。若vivj，则称ek与vi的关联次数为2，并称ek为环。若端点vl不与边ek关联，则称ek与vl的关联次数为0。设D为有向图，ekE，称vi,vj为ek的端点。若vivj，则称ek为D中的环。无论在无向图中还是在有向图中，

5、无边关联的顶点均称为孤立点。,相邻与邻接,设无向图G，vi，vjV，ek，elE。若etE，使得et(vi，vj)，则称vi与vj是相邻的。若ek与el至少有一个公共端点，则称ek与el是相邻的。设有向图D，vi，vjV，ek，elE。若etE，使得et，则称vi为et的始点，vj为et的终点，并称vi邻接到vj，vj邻接于vi。若ek的终点为el的始点，则称ek与el相邻。,邻域,设无向图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的后继元

6、集，记做+D(v)。称u|uVEuv为v的先驱元集，记做-D(v)。称+D(v)-D(v)为v的邻域，记做ND(v)。称ND(v)v为v的闭邻域，记做ND(v)。,举例,NG(v1),+D(d),v2，v5,NG(v1),v1，v2，v5,IG(v1),e1，e2，e3,c,-D(d),a，c,ND(d),a，c,ND(d),a，c，d,简单图与多重图,定义14.3 在无向图中，关联一对顶点的无向边如果多于1条，则称这些边为平行边，平行边的条数称为重数。在有向图中，关联一对顶点的有向边如果多于1条，并且这些边的始点和终点相同(也就是它们的方向相同)，则称这些边为平行边。含平行边的图称为多重图。

7、既不含平行边也不含环的图称为简单图。例如：在图14.1中，(a)中e5与e6是平行边，(b)中e2与e3是平行边，但e6与e7不是平行边。(a)和(b)两个图都不是简单图。,顶点的度数,定义14.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)。,图的度数的相关概念,在无向图G中，最大度(G)maxd(v)|vV

8、(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的顶点为悬挂顶点，与它关联的边称为悬挂边。度为偶数(奇数)的顶点称为偶度(奇度)顶点。,图的度数举例,d(v1)4(注意，环提供2度)，4，1，v4是悬挂顶点，e7是悬挂边。,d+(a)4，d-(a)1(环e1提供出度1，提供入度1)，d(a)4+15。5，3，+4(在a点达到)+0(在b点达到)-3(在b点达到)-1(在a和c点达到),握手定理,定理1

10、由于意见不同，是否可能每个人恰好与其他5个人意见一致？解答：不可能。考虑一个图，其中顶点代表人，如果两个人意见相同，可用边连接，所以每个顶点都是奇数度。存在奇数个度数为奇数的图，这是不可能的。说明：(1)很多离散问题可以用图模型求解。(2)为了建立一个图模型，需要决定顶点和边分别代表什么。(3)在一个图模型中，边经常代表两个顶点之间的关系。,度数列,设G为一个n阶无向图，Vv1,v2,vn，称d(v1)，d(v2)，d(vn)为G的度数列。对于顶点标定的无向图，它的度数列是唯一的。反之，对于给定的非负整数列dd1,d2,dn，若存在Vv1,v2,vn为顶点集的n阶无向图G，使得d(vi)di，

11、则称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,34,0,2,11,3,1,2,可图化的充要条件,定理14.3 设非负整数列d(d1，d2，dn)，则d是可图化的当且仅当,证明必要性。由握手定理显然得证。充分性。由已知条件可知，d中有偶数个奇数度点。奇数

12、度点两两之间连一边，剩余度用环来实现。,定理14.3的证明,由握手定理可知必然性显然。下面证明充分性。由已知条件可知，d中有2k(0kn/2)个奇数，不妨设它们为d1，d2，dk，dk+1，dk+2，d2k。可用多种方法做出n阶无向图G，Vv1,v2,vn。比如边集如下产生：在顶点vr与vr+k之间连边，r1,2,k。若di为偶数，令didi，若di为奇数，令didi-1，得d(d1，d2，dn)，则di均为偶数。再在vi处做出di/2条环,i1,n，将所得各边集合在一起组成E，则G的度数列为d。其实，di为偶数时，d(vi)2di/22di/2di，当di为奇数时，d(vi)1+2di/21

13、+di1+di-1di，这就证明了d是可图化的。,可图化举例,由定理14.3立即可知，(3,3,2,1)，(3,2,2,1,1)等是不可图化的，(3,3,2,2)，(3,2,2,2,1)等是可图化的。,定理14.4,定理14.4 设G为任意n阶无向简单图，则(G)n-1。证明因为G既无平行边也无环，所以G中任何顶点v至多与其余的n-1个顶点均相邻，于是d(v)n-1，由于v的任意性，所以(G)n-1。例14.2 判断下列各非负整数列哪些是可图化的？哪些是可简单图化的？(1)(5,5,4,4,2,1)不可图化。(2)(5,4,3,2,2)可图化，不可简单图化。若它可简单图化，设所得图为G，则(G

14、)max5,4,3,2,25，这与定理14.4矛盾。,例14.2,(3)(3,3,3,1)可图化，不可简单图化。假设该序列可以简单图化，设G以该序列为度数列。不妨设Vv1,v2,v3,v4且 d(v1)d(v2)d(v3)3,d(v4)1，由于d(v4)1，因而v4只能与v1，v2，v3之一相邻，于是v1，v2，v3不可能都是3度顶点，这是矛盾的，因而(3)中序列也不可简单图化。,(4)(d1,d2,dn)，d1d2dn1 且为偶数。,可图化，不可简单图化。,例14.2,(5)(4,4,3,3,2,2)可简单图化。下图中两个6阶无向简单图都以(5)中序列为度数列。,图的同构,定义14.5 设

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

16、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)/2,K5,3阶有向完全图,4阶竞赛图,正则图,定义14.7 设G为n阶无向简单图，若vV(G)，均有d(v)k，则称G为k-正则图。举例n阶零图是0-正则图n阶无向完全图是(n-1)-正则图彼得森图是3-正则图说明n阶k-正则图中，边数mkn/2。当k为奇数时，n必为偶数。,子图,定义14.

17、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为(2)中图所示。取E1e1,e3，则E1的导出子图GE1为(3)中图所示。,例14.3,(1)画出

18、4阶3条边的所有非同构的无向简单图。由握手定理可知，所画的无向简单图各顶点度数之和为236，最大度小于或等于3。于是所求无向简单图的度数列应满足的条件是，将6分成4个非负整数，每个整数均大于或等于0且小于或等于3，并且奇数的个数为偶数。将这样的整数列排出来只有下面三种情况：,(1)2，2，1，1(2)3，1，1，1(3)2，2，2，0,将每种度数列所有非同构的图都画出来即得所要求的全部非同构的图。,对于给定的正整数n和m(mn(n-1)/2)，构造出所有非同构的n阶m条边的所有非同构的无向(有向)简单图，这是目前还没有解决的难题。,例14.3,(2)画出3阶2条边的所有非同构的有向简单图。由握

19、手定理可知，所画有向简单图各顶点度数之和为4，最大出度和最大入度均小于或等于2。度数列及入度出度列为,1,2,1,入度列为 0,1,1 或 0,2,0 或 1,0,1,出度列为 1,1,0 或 1,0,1 或 0,2,0,2,2,0,入度列为 1,1,0,出度列为 1,1,0,定义14.9,定义14.9 设G为n阶无向简单图，以V为顶点集，以所有使G成为完全图Kn的添加边组成的集合为边集的图，称为G的补图，记作G。若图GG，则称为G是自补图。,(1)为自补图(2)和(3)互为补图,定义14.10,定义14.10 设G为无向图。(1)设eE，用G-e表示从G中去掉边e，称为删除e。设E E，用G

20、-E 表示从G中删除E 中所有的边，称为删除E。(2)设vV，用G-v表示从G中去掉v及所关联的一切边，称为删除顶点v。设V V，用G-V 表示从G中删除V 中所有顶点，称为删除V。(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)，称为加新边。说明在收缩边和加新边过程中可能产生环和平行边。,举例,G,Ge5,Ge1,e4,Gv5,Gv4,v5,Ge5,14.2 通路

21、与回路,定义14.11 设G为无向标定图，G中顶点与边的交替序列vi0ej1vi1ej2vi2ejivil称为vi0到vil的通路，其中，vir-1,vir为ejr的端点，r 1，2，l，vi0，vil分别称为的始点与终点，中边的条数称为它的长度。若vi0vil，则称通路为回路。若的所有边各异，则称为简单通路，又若vi0vil，则称为简单回路。若的所有顶点(除vi0与vij可能相同外)各异，所有边也各异，则称为初级通路或路径，又若vi0vil，则称为初级回路或圈。将长度为奇数的圈称为奇圈，长度为偶数的圈称为偶圈。,关于通路与回路的说明,在初级通路与初级回路的定义中，仍将初级回路看成初级通路(路

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

23、,vi2,vil。为了写出非标定图中的通路(回路)，可以先将非标定图标成标定图，再写出通路与回路。在非简单标定图中，当只用顶点序列表示不出某些通路(回路)时，可在顶点序列中加入一些边(这些边是平行边或环)，可称这种表示法为混合表示法。,定理14.5,定理14.5 在n阶图G中，若从顶点vi到vj（vivj）存在通路，则从vi到vj存在长度小于或等于n-1的通路。证明设v0e1v1e2elvl(v0vi,vlvj)为G中一条长度为l的通路，若ln-1，则满足要求，否则必有l+1n，即上的顶点数大于G中的顶点数，于是必存在k,s,0ksl，使得 vsvk,即在上存在vs到自身的回路Csk,在上删除

24、Csk上的一切边及除vs外的一切顶点，得v0e1v1e2vkes+1 elvl,仍为vi到vj的通路，且长度至少比减少1。若还不满足要求，则重复上述过程，由于G是有限图，经过有限步后，必得到vi到vj长度小于或等于n-1的通路。,定理14.6,推论在n阶图G中，若从顶点vi到vj（vivj）存在通路，则vi到vj一定存在长度小于或等于n-1的初级通路（路径）。定理14.6 在一个n阶图G中，若存在vi 到自身的回路，则一定存在vi 到自身长度小于或等于n的回路。推论在一个n阶图G中，若存在vi 到自身的简单回路，则一定存在vi 到自身长度小于或等于n的初级回路。,例14.4,例14.4 无

25、向完全图Kn(n3)中有几种非同构的圈？解答长度相同的圈都是同构的，因而只有长度不同的圈才是非同构的，易知Kn(n3)中含长度为3，4，n的圈，所以Kn(n3)中有n-2种非同构的圈。,例14.5,例14.5 无向完全图K3的顶点依次标定为a,b,c。在定义意义下K3中有多少个不同的圈？解答在同构意义下，K3中只有一个长度为3的圈。但在定义意义下，不同起点(终点)的圈是不同的，顶点间排列顺序不同的圈也看成是不同的，因而K3中有6个不同的长为3的圈：abca，acba，bacb，bcab，cabc，cbac如果只考虑起点(终点)的差异，而不考虑顺时针逆时针的差异，应有3种不同的圈，当然它们都是同

26、构的，画出图来只有一个。,14.3 图的连通性,无向图的连通性无向图中顶点之间的短程线及距离无向图的连通程度：点割集、割点、边割集、割边、连通度有向图的连通性及判别方法扩大路径法与极大路径二部图及其判别方法,无向图的连通性,定义14.12 设无向图G，u,vV，若u,v之间存在通路，则称u,v是连通的，记作uv。vV，规定vv。无向图中顶点之间的连通关系（u,v）|u,vV且u与v之间有通路是自反的、对称的、传递的，因而是V上的等价关系。,连通图与连通分支,若无向图G是平凡图或G中任何两个顶点都是连通的，则称G为连通图，否则称G是非连通图或分离图。说明：完全图Kn(n1)都是连通图零图Nn(n

27、2)都是分离图。定义14.13 设无向图G，V关于顶点之间的连通关系的商集V/V1,V2,Vk，Vi为等价类，称导出子图GVi(i1,2,k)为G的连通分支，连通分支数k常记为p(G)。说明若G为连通图，则p(G)1。若G为非连通图，则p(G)2。在所有的n阶无向图中，n阶零图是连通分支最多的，p(Nn)n。,无向图中顶点之间的短程线及距离,定义14.14 设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)

28、具有对称性，d(u,v)d(v,u)。(3)满足三角不等式：u,v,wV(G)，则d(u,v)+d(v,w)d(u,w)说明：在完全图Kn(n2)中，任何两个顶点之间的距离都是1。在n阶零图Nn(n2)中，任何两个顶点之间的距离都为。,如何定义连通度,问题：如何定量地比较无向图的连通性的强与弱？点连通度：为了破坏连通性，至少需要删除多少个顶点？边连通度：为了破坏连通性，至少需要删除多少条边？“破坏连通性”是指“变得更加不连通”。,无向图的点割集,定义14.15 设无向图G，若存在V V，且V，使得p(G-V)p(G)，而对于任意的V V，均有p(G-V)p(G)，则称V 是G的点割集。若V 是

29、单元集，即V v，则称v为割点。,v2,v4,v3,v5都是点割集v3,v5都是割点v1与v6不在任何割集中。,无向图的边割集,定义14.16设无向图G，若存在E E，且E，使得p(G-E)p(G)，而对于任意的E E，均有p(G-E)p(G)，则称E是G的边割集，或简称为割集。若E 是单元集，即E e，则称e为割边或桥。,e6,e5,e2,e3,e1,e2,e3,e4,e1,e4,e1,e3,e2,e4都是割集，e6,e5是桥。,点连通度,定义14.17设G为无向连通图且为非完全图，则称 K(G)min|V|V 为G的点割集为G的点连通度，简称连通度。说明连通度是为了产生一个不连通图需要删

30、去的点的最少数目。规定完全图Kn(n1)的点连通度为n-1，规定非连通图的点连通度为0，若K(G)k，则称G是k-连通图，k为非负整数。说明K(G)有时简记为K。上例中图的点连通度为1，此图为1-连通图。K5的点连通度K4，所以K5是1-连通图，2-连通图，3-连通图，4-连通图。若G是k-连通图（k1）则在G中删除任何k-1个顶点后，所得图一定还是连通的。,边连通度,定义14.18 设G是无向连通图，称(G)min|E|E 是G的边割集为G的边连通度。规定非连通图的边连通度为0。若(G)r，则称G是r 边-连通图。说明(G)也可以简记为。若G是 r 边-连通图，则在G中任意删除r-1条边后，

31、所得图依然是连通的。完全图Kn的边连通度为n-1，因而Kn是r边-连通图，0rn-1。图14.8中图的边连通度1，它只能是1边-连通图。,例14.6,求所示各图的点连通度，边连通度，并指出它们各是几连通图及几边连通图。最后将它们按点连通程度及边连通程度排序。,K4,K3,K2,K1,K=1=2,K2,K0,K0,例14.6的解答,设第i个图的点连通度为Ki，边连通度为i，I1,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-连

32、通图，k边-连通图，k1,2。(4)是1-连通图，1边-连通图。(5)是1-连通图，k边-连通图，k1,2。(6)是k-连通图，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)。,定理14.7,定理14.7 对于任何无向图G，有 K(G)(G)(G)例14.7(1)给出一些无向简单图，使得 K。(2)给出一些无向简单图，使得 K。解答(1)n阶无向完全图Kn和n阶零图Nn都满足要求。(2)在两个Kn(n4)之间放置一个顶点v，使v

33、与两个Kn中的每一个的任意两个不同的顶点相邻，所得简单图满足要求。因为这样的图中有一个割点，所以点连通度为1，又因为无桥，而有两条边组成的边割集，所以边连通度为2，当n4时，3，当n5时，4。,有向图的连通性,定义14.19 设D为一个有向图。vi,vjV，若从vi到vj存在通路，则称vi可达vj，记作vivj，规定vi总是可达自身的，即vivi。若vivj且vjvi，则称vi与vj是相互可达的，记作vi vj。规定vivi。说明与都是V上的二元关系，并且不难看出是V上的等价关系。定义14.20 设D为有向图，vi,vjV，若vivj，称vi到vj长度最短的通路为vi到vj的短程线，短程线的

34、长度为vi到vj的距离，记作d。说明与无向图中顶点vi与vj之间的距离d(vi,vj)相比，d除无对称性外，具有d(vi,vj)所具有的一切性质。,连通图,定义14.21 设D为一个有向图。若D的基图是连通图，则称D是弱连通图，简称为连通图。若vi,vjV，vivj与vjvi至少成立其一，则称D是单向连通图。若均有vi vj，则称D是强连通图。说明强连通图一定是单向连通图，单向连通图一定是弱连通图。,强连通图,单向连通图,弱连通图,强连通图与单向连通图的判定定理,定理14.8 设有向图D，Vv1,v2,vn。D是强连通图当且仅当D中存在经过每个顶点至少一次的回路。证明充分性显然。下面证明

35、必要性。由D的强连通性可知，vivi+1，i1,2,n-1。设i为vi到vi+1的通路。又因为vnv1，设n为vn到v1的通路，则1,2,n-1,n所围成的回路经过D中每个顶点至少一次。定理14.9 设D是n阶有向图，D是单向连通图当且仅当D中存在经过每个顶点至少一次的通路。证明略。,强连通图与单向连通图的判定定理,定理14.8 设有向图D，Vv1,v2,vn。D是强连通图当且仅当D中存在经过每个顶点至少一次的回路。证明充分性显然。下面证明必要性。由D的强连通性可知，vivi+1，i1,2,n-1。设i为vi到vi+1的通路。又因为vnv1，设n为vn到v1的通路，则1,2,n-1,n所围成

36、的回路经过D中每个顶点至少一次。定理14.9 设D是n阶有向图，D是单向连通图当且仅当D中存在经过每个顶点至少一次的通路。证明略。问题设有向图D是单向连通图，但不是强连通图，问在D中至少加几条边所得图D 就能成为强连通图？,扩大路径法,设G为n阶无向图，E，设l为G中一条路径，若此路径的始点或终点与通路外的顶点相邻，就将它们扩到通路中来。继续这一过程，直到最后得到的通路的两个端点不与通路外的顶点相邻为止。设最后得到的路径为l+k(长度为l的路径扩大成了长度为l+k的路径)，称l+k为“极大路径”，称使用此种方法证明问题的方法为“扩大路径法”。有向图中可以类似地讨论，只须注意，在每步扩大中保持

37、有向边方向的一致性。,关于极大路径的说明,由某条路经扩大出的极大路径不唯一。极大路径不一定是图中最长的路径。,例14.8,例14.8 设G为n（n4）阶无向简单图，(G)3。证明G中存在长度大于或等于4的圈。证明不妨设G是连通图，否则，因为G的各连通分支的最小度也都大于或等于3，因而可对它的某个连通分支进行讨论。设u,v为G中任意两个顶点，由G是连通图，因而u,v之间存在通路，由定理14.5的推论可知，u,v之间存在路径，用“扩大路径法”扩大这条路径，设最后得到的“极大路径”为lv0v1vl，易知l3。若v0与vl相邻，则l(v0,vl)为长度大于或等于4的圈。否则，由于d(v0)(G)3，

38、因而v0除与l上的v1相邻外，还存在l上的顶点vk(k1)和vt(kt l)与v0相邻，则v0v1vkvtv0为一个圈且长度大于或等于4，见图。,二部图,定义14.22 设G为一个无向图，若能将V分成V1和V2(V1V2V,V1V2)，使得G中的每条边的两个端点都是一个属于V1，另一个属于V2，则称G为二部图（或称二分图，偶图等），称V1和V2为互补顶点子集。常将二部图G记为。若G是简单二部图，V1中每个顶点均与V2中所有顶点相邻，则称G为完全二部图，记为Kr,s，其中r|V1|，s|V2|。说明n阶零图为二部图。,二部图举例,K6的子图,K6的子图,K3,3,K2,3,K3,3,K2,3,二

39、部图的判定定理,定理14.10 一个无向图G是二部图当且仅当G中无奇数长度的回路。证明必要性。若G中无回路，结论显然成立。若G中有回路，只需证明G中无奇圈。设C为G中任意一圈，令Cvi1vi2vilvi1，易知 l2。不妨设vi1V1，则必有vilV-V1=V2，而l必为偶数，于是C为偶圈，由C的任意性可知结论成立。,二部图的判定定理,充分性。不妨设G为连通图，否则可对每个连通分支进行讨论。设v0为G中任意一个顶点，令V1v|vV(G)d(v0,v)为偶数V2v|vV(G)d(v0,v)为奇数易知，V1,V2,V1V2，V1V2V(G)。下面只要证明V1中任意两顶点不相邻,V2中任意两点也不相

40、邻。若存在vi,vjV1相邻，令(vi,vj)e，设v0到vi,vj的短程线分别为i,j，则它们的长度d(v0,vi),d(v0,vj)都是偶数，于是ije中一定含奇圈，这与已知条件矛盾。类似可证，V2中也不存在相邻的顶点，于是G为二部图。,14.4 图的矩阵表示,定义14.23 设无向图G，Vv1,v2,vn，Ee1,e2,em，令mij为顶点vi与边ej的关联次数，则称(mij)nm为G的关联矩阵，记作M(G)。,有向图的关联矩阵,定义14.24 设有向图D中无环，Vv1,v2,vn，Ee1,e2,em，令,则称(mij)nm为D的关联矩阵，记作M(D)。,有向图的邻接矩阵,定义14.25

41、设有向图D，Vv1,v2,vn，Ee1,e2,，em，令aij(1)为顶点vi邻接到顶点vj边的条数，称(aij(1)nn为D的邻接矩阵，记作A(D)，或简记为A。,有向图中的通路数与回路数,定理14.11 设A为n阶有向图D的邻接矩阵,则Al(l1)中元素等于D中vi到vj长度为 l 的通路(含回路)数,等于vi到自身长度为l 的回路数,等于D中长度为 l 的通路(含回路)总数,等于D中长度为 l 的回路总数.,有向图中的通路数与回路数(续),推论设Bl=A+A2+Al(l1),则Bl中元素等于D中vi到vj长度小于等于 l 的通路(含回路)数,等于D中vi到vi长度小于等于 l 的

42、回路数,等于D中长度小于等于l 的通路(含回路)数,为D中长度小于等于l 的回路数.,实例(续),说明:在这里,通路和回路数是定义意义下的,v1到v2长为3的通路有1条v1到v3长为3的通路有1条v1到自身长为3的回路有2条D中长为3的通路共有15条,其中回路3条,有向图的可达矩阵,定义14.26 设D为有向图。Vv1,v2,vn，令,pij,1 vi 可达 vj,0 否则,称(pij)nn为D的可达矩阵，记作P(D)，简记为P。,14.5 图的运算,定义14.27 设G1，G2为两个图。若V1V2，则称G1与G2是不交的。若E1E2，则称G1与G2是边不交的或边不重的。说明：不交的图，必然是

43、边不交的，但反之不真。,图的运算,定义14.28 设G1，G2为不含孤立点的两个图（它们同为无向图或同为有向图）。(1)称以E1E2为边集，以E1E2中边关联的顶点组成的集合为顶点集的图为G1与G2的并图，记作G1G2。(2)称以E1-E2为边集，以E1-E2中边关联的顶点组成的集合为顶点集的图为G1与G2的差图，记作G1-G2。(3)称以E1E2为边集，以E1E2中边关联的顶点组成的集合为顶点集的图为G1与G2的交图，记作G1G2。(4)称以E1E2为边集（为集合之间的对称差运算），以E1E2中边关联的顶点组成的集合为顶点集的图为G1与G2的环和，记作G1G2。,定义14.28的说明,(1)

44、若G1G2，则G1G2G1G2G1(G2)G1-G2G2-G1G1G2这就是在图的定义中给出空图概念的原因。(2)当G1与G2边不重时，G1G2G1-G2G1G2-G1G2G1G2G1G2(3)图之间环和的定义也可以用并、交、差给出，即G1G2(G1G2)-(G1G2),基本要求,理解与图的定义有关的诸多概念，以及它们之间的相互关系。深刻理解握手定理及其推论的内容，并能熟练地应用它们。深刻理解图同构、简单图、完全图、正则图、子图、补图、二部图等概念及其它们的性质和相互关系，并能熟练地应用这些性质和关系。深刻理解通路与回路的定义、相互关系及其分类，掌握通路与回路的各种不同的表示方法。理解无向图的点连通度、边连通度等概念及其之间的关系，并能熟练地求出给定的较为简单的图的点连通度与边连通度。理解有向图连通性的概念及其分类，掌握判断有向连通图类型的方法。,作业,习题十四3(b)、8、21,

展开阅读全文