《第9章 图论.ppt》由会员分享，可在线阅读，更多相关《第9章 图论.ppt（69页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、引引 言言图论是离散数学的重要组成部分，是近代应用数学的重要分支。人们常称图论是离散数学的重要组成部分，是近代应用数学的重要分支。人们常称1736年是图论历史元年，因为在这一年瑞士数学家欧拉（年是图论历史元年，因为在这一年瑞士数学家欧拉（Euler）发表了图论）发表了图论的首篇论文的首篇论文哥尼斯堡七桥问题无解哥尼斯堡七桥问题无解，所以人们普遍认为欧拉是图论的，所以人们普遍认为欧拉是图论的创始人。创始人。1936年，匈牙利数学家寇尼格（年，匈牙利数学家寇尼格（Konig）出版了图论的第一部专著）出版了图论的第一部专著有限图有限图与无限图理论与无限图理论，这是图论发展史上的重要的里程碑，它标志着
2、图论将进入突，这是图论发展史上的重要的里程碑，它标志着图论将进入突飞猛进发展的新阶段。飞猛进发展的新阶段。近近40年来，随着计算机科学的发展，图论更以惊人的速度向前发展，有人形年来，随着计算机科学的发展，图论更以惊人的速度向前发展，有人形容说：真是异军突起，活跃非凡。其主要原因有二：其一，计算机科学的发展容说：真是异军突起，活跃非凡。其主要原因有二：其一，计算机科学的发展为图论的发展提供了计算工具；其二，现代科学技术的发展需要借助图论来描为图论的发展提供了计算工具；其二，现代科学技术的发展需要借助图论来描述和解决各类课题中的各种关系，从而推动科学技术不断地攀登新的高峰。述和解决各类课题中的各种
3、关系，从而推动科学技术不断地攀登新的高峰。作为描述事务之间关系的手段或称工具，目前，图论在许多领域，诸如，计作为描述事务之间关系的手段或称工具，目前，图论在许多领域，诸如，计算机科学、物理学、化学、运筹学、信息论、控制论、网络通讯、社会科学以算机科学、物理学、化学、运筹学、信息论、控制论、网络通讯、社会科学以及经济管理、军事、国防、工农业生产等方面都得到广泛的应用，也正是因为及经济管理、军事、国防、工农业生产等方面都得到广泛的应用，也正是因为在众多方面的应用中，图论自身才得到了非常迅速的发展。在众多方面的应用中，图论自身才得到了非常迅速的发展。本部分主要包括图的基本概念（第九章）、欧拉图与哈密
4、顿图（第十一章）、本部分主要包括图的基本概念（第九章）、欧拉图与哈密顿图（第十一章）、树（第十章树（第十章 9.1 图图一无向图与有向图一无向图与有向图1无序积与多重集无序积与多重集设A，B为任意的两个集合，称a,b|aAbB为A与B的无序积无序积，记作A&B.为方便起见，将无序积中的无序对a,b记为(a,b),并且允许a=b.需要指出的是，无论a,b是否相等，均有(a,b)=(b,a),因而A&B=B&A.元素可以重复出现的集合称为多重集合多重集合或者多重集多重集，某元素重复出现的次数称为该元素的重复度重复度。例如，在多重集合a,a,b,b,b,c,d中，a,b,c,d的重复度分别为2,3,
5、1,1.2无向图与有向图的定义及表示法无向图与有向图的定义及表示法 定义定义9.1一个无向图无向图是一个有序的二元组,记作G，其中（1）V称为顶点集，其元素称为顶点或结点。（2）E称为边集，它是无序积V&V的多重子集，其元素称为无向边，简称边。定义定义9.2一个有向图有向图是一个有序的二元组，记作D，其中（1）V同无向图。（2）E为边集，它是笛卡儿积VV的多重子集，其元素称为有向边，简称边。上面给出了无向图和有向图的集合定义，但人们总是用图形来表示它们，即用小圆圈（或实心点）表示顶点，用顶点之间的连线表示无向边，用有方向的连线表示有向边。例例9.1(1)给定无向图G=，其中，V=v1,v2,v
6、3,v4,v5，E=(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5).(2)给定有向图D=，其中，V=a,b,c,d，E=,.画出G与D的图形。解解图9.1中(1),(2)分别给出了无向图G和有向图D的图形。（板书画图）与定义9.1和定义9.2有关的还有下面一些概念和规定。1n阶图阶图在图的定义中，用G表示无向图，D表示有向图，但有时用G泛指图(无向的或有向的)，可是D只能表示有向图。另外，为方便起见，有时用V(G)，E(G)分别表示G的顶点集和边集，若|V(G)|=n,则称G为n阶图阶图，对有向图可做类似规定。2有限图有限图若|V
7、(G)|与|E(G)|均为有限数，则称G为有限图有限图，本课件中只讨论有限图。3n阶零图与平凡图阶零图与平凡图 在图在图G中，若边集中，若边集E(G)=,则称则称G为零图，此时，又若为零图，此时，又若G为为n阶图，则称阶图，则称G为为n阶零图，记作阶零图，记作Nn，特别地，称，特别地，称N1为平凡为平凡图。图。4空图空图 在图的定义中规定顶点集在图的定义中规定顶点集V为非空集，但在图的运算中可为非空集，但在图的运算中可能产生顶点集为空集的运算结果，为此规定定点集为空集的能产生顶点集为空集的运算结果，为此规定定点集为空集的图为空图，并将空图记为图为空图，并将空图记为。5标定图与非标定图、基图标定
8、图与非标定图、基图 将图的集合定义转化成图形表示之后，常用将图的集合定义转化成图形表示之后，常用e k表示无向表示无向边（边（v i，v j）（或有向边）（或有向边）,并称顶点或边用字母并称顶点或边用字母标定的图为标定图，否则称为非标定图。另外将有向图各有标定的图为标定图，否则称为非标定图。另外将有向图各有向边均改成无向边后的无向图称为原来图的基图。易知标定向边均改成无向边后的无向图称为原来图的基图。易知标定图与非标定图是可以相互转化的，任何无向图图与非标定图是可以相互转化的，任何无向图G的各边均加的各边均加上箭头就可以得到以上箭头就可以得到以G为基图的有向图。为基图的有向图。6关联与关联次数
9、、环、孤立点关联与关联次数、环、孤立点 设G=为无向图，ek=(vi，vj)E，则称vi，vj为ek的端点，ek与vi或ek与vj是彼此相关联关联的。若vivj，则称ek与vi或ek与vj的关联次数关联次数为1，若vi=vj，则称ek与vi的关联次数为2，并称ek为环环。任意的vlV，若vlvi且vlvj，则称ek与vl的关联次数为0。设D=为有向图，ek=E，称vi，vj为ek的端点，若vi=vj，则称ek为D中的环。无论在无向图中还是在有向图中，无边关联的顶点均称孤立点孤立点。7相邻与邻接相邻与邻接设无向图G=，vi，vjV，ek，elE.若etE，使得et=（vi，vj），则称vi与vj
10、是相邻相邻的。若ek与el至少有一个公共端点，则称ek与el是相邻的。设有向图D=，vi，vjV，ek，elE.若etE，使得et=，则称vi为et的始点，vj为et的终点，并称vi邻接到邻接到vj，vj邻接于邻接于vi。若ek的终点为el的始点，则称ek与el相邻。8邻域与闭邻域、先驱元集与后继元集、关联集邻域与闭邻域、先驱元集与后继元集、关联集 设无向图设无向图G=，vV，称称 u|uV (u,v)E uv 为为v的邻域，记做的邻域，记做NG(v).并称并称 N G(v)v 为为v的闭邻域，记做的闭邻域，记做 G(v).称称 e|e E e与与v相关联相关联 为为v的关联集，记做的关联集，
11、记做IG(v).设有向图设有向图D=，vV，称称 u|uV E uv 为为v的后继元集，的后继元集，记做记做(v).称称 u|uV E uv 为为v的先驱元集，的先驱元集，记做记做(v).称称 (v)(v)为为v的邻域，记做的邻域，记做ND(v).称称 ND(v)v 为为v的闭邻域，记做的闭邻域，记做 D(v).在图在图9.1的的(1)图中，图中，NG(v1)=v2，v5，G(v1)=v1，v2，v5，IG(v1)=e1，e2，e3.在在(2)图中，图中，(d)=c，(d)=a，c，ND(d)=a，c，D(d)=a，c，d.9图的数学定义与表示法图的数学定义与表示法给定图G的数学定义，按定义的
12、规定，一定能画出它的图形与之对应，但由于顶点放置的位置可以不同，边的曲直可以不同，所以不同的人画出的图形形状可能不同，但顶点与边之间的关联关系是绝对相同的。反之给定某图G的图形，若非标定图，先将顶点与边标定，则能唯一地写出G的数学定义形式。二简单图与多重图 定义定义9.3:在无向图中，关联一对顶点的无向边如果多于1条，则称这些边为平行边平行边，平行边的条数称为重数重数。在有向图中，关联一对顶点的有向边如果多于1条，并且这些边的始点和终点相同(也就是它们的方向相同)，则称这些边为平行边平行边。含平行边的图称为多重图多重图，既不含平行边也不含环的图称为简单图简单图。在图9.1中，(1)中e5与e6
13、是平行边，在(2)中，e2与e3是平行边，注意，e6与e7不是平行边。(1)，(2)两个图都不是简单图。三顶点的度数与握手定理1顶点的度数顶点的度数 定义定义9.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).2握手定理握手定理定理定理9.1(握手定理握手定理)设G=为任意无向图，V=v1,v2,
14、vn，|E|=m，则=2m定理定理9.2(握手定理握手定理)设D=为任意有向图，V=v1,v2,vn，|E|=m，则=2m，且=m.握手定理的推论握手定理的推论 任何图(无向的或有向的)中，奇度顶点的个数是偶数。下面给出与顶点度数有关的概念。1无向图无向图G中的最大度和最小度中的最大度和最小度在无向图G中，令(G)=maxd(v)|vV(G)(G)=mind(v)|vV(G)称(G)，(G)分别为G的最大度最大度和最小度最小度。在不引起混淆的情况下，将(G)，(G)分别简记为和.2有向图有向图D中的最大度、最大出度、最大入度与最小度、最中的最大度、最大出度、最大入度与最小度、最小出度、最小入度
15、小出度、最小入度在有向图D中，类似无向图，可以定义最大度(D)，最小度(D)，另外，令+(D)=maxd+(v)|vV(D)+(D)=mind+(v)|vV(D)-(D)=maxd-(v)|vV(D)-(D)=mind-(v)|vV(D)分别称为D的最大出度最大出度，最小出度最小出度，最大入度最大入度，最小入度最小入度。以上记号可分别简记为，+，+，-，-.3悬挂顶点与悬挂边；奇度顶点与偶度顶点悬挂顶点与悬挂边；奇度顶点与偶度顶点称度数为1的顶点为悬挂顶点悬挂顶点，与它关联的边称为悬挂边悬挂边。度为偶数(奇数)的顶点称为偶度偶度(奇度奇度)顶点顶点。在图9.1中，(1)的d(v1)=4(注意，
16、环提供2度)，=4，=1，v4是悬挂顶点，e7是悬挂边。(2)的d+(a)=4，d-(a)=1(环e1提供出度1，提供入度1)，d(a)=4+1=5。=5，=3，+=4(在a点达到)，+=0(在b点达到)，-=3(在b点达到)，-=1(在a和c点达到)。v4度数列度数列设G=为一个n阶无向图,V=v1,v2,vn,称d(v1),d(v2),d(vn)为G的度度数列数列，对于顶点标定的无向图，它的度数列是唯一的。设D=为一个n阶有向图，V=v1,v2,vn，称d(v1),d(v2),d(vn)为D的度数列，另外称d+(v1),d+(v2),d+(vn)与d-(v1),d-(v2),d-(vn)分
17、别为D的出度列出度列和入度列入度列。在图9.1(1)中，按顶点的标定顺序，度数列为4,4,2,1,3.在(2)中，按字母顺序，度数列，出度列，入度列分别为5,3,3,3；4,0,2,1；1,3,1,2.5可图化的与可简单图化的非负整数列可图化的与可简单图化的非负整数列对于给定的非负整数列d=(d1,d2,dn)，若存在以V=v1,v2,vn为顶点集的n阶无向图G，使得d(vi)=di，则称d是可图化的可图化的。特别地，若所得图是简单图，则称d是可简可简单图化的单图化的。d=(d1,d2,dn)是否为可图化的，可由下面定理判别。定理定理9.3设非负整数列d=(d1，d2，dn)，则d是可图化的当
18、且仅当=0(mod2).由定理9.3立即可知，(3，3，2，1)，(3，2，2，1，1)等是不可图化的，而(3，3，2，2)，(3，2，2，2，1)等是可图化的。定理定理9.4 设G为任意n阶无向简单图，则(G)n-1.例例92判断下列各非负整数列哪些是可图化的？哪些是可简单图化的？(1)(5,5,4,4,2,1)(2)(5,4,3,2,2)(3)(3,3,3,1)(4)(d1,d2,dn)，d1d2dn1且为偶(5)(4,4,3,3,2,2)解解:除(1)中序列不可图化外，其余各序列都可图化。但除了(5)中序列外，其余的都是不可简单图化的。(2)中序列有5个数，若它可简单图化，设所得图为G，
19、则(G)=max5,4,3,2,2=5，这与定理14.4矛盾。所以(2)中序列不可简单图化。类似可证(4)中序列不可简单图化。假设(3)中序列可以简单图化，设G=以(3)中序列为度数列。不妨设V=v1，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)中序列也不可简单图化。(5)中序列是可简单图化的，图14.2中两个6阶无向简单图都以(5)中序列为度数列。四图的同构1两图同构的定义两图同构的定义定义定义9.5 设G1=，G2=为两个无向图(两个有向图)
20、，若存在双射函数f：V1V2，对于 vi，vjV1，(vi，vj)E1(E1)当且仅当(f(vi)，f(vj)E2(E2)，并且(vi，vj)()与(f(vi)，f(vj)()的重数相同，则称G1与G2是同构同构的，记做G1G2.v2图之间的同构关系是等价关系图之间的同构关系是等价关系图之间的同构关系可看成全体图集合上的二元关系，这个二元关系具有自反性，对称性和传递性，因而它是等价关系。在这个等价关系的每一等价类中均取一个非标定图作为一个代表，凡与它同构的图，在同构的意义之下都可以看成一个图，在图9.3中，(1)，(2)，(3)可以看成一个图，它们都是彼得松图，其中的(1)可看成这类图的代表。
21、提到彼得松图，一般是指(1)中图。至此，可以这样说，在图同构的意义下，图的数学定义与图形表示是一一对应的。关于图之间的同构问题还应该指出以下两点：a到目前为止，人们还没有找到判断两个图是否同构的好的算法，还只能根据定义看是否能找到满足条件的双射函数，显然这是困难的。b需要注意的是，不要将两个图同构的必要条件当成充分条件。若G1G2，则它们的阶数相同，边数相同，度数列相同，等等。破坏这些必要条件的任何一个，两个图就不会同构，但以上列出的条件都满足，两个图也不一定同构，在图9.2中的两个图，有相同的度数列，但它们不同构。五完全图与正则图定义定义9.6 设G为n阶无向简单图，若G中每个顶点均与其余的
22、n-1个顶点相邻，则称G为n阶无向完阶无向完全图全图，简称n阶完全图，记做Kn(n1)。设D为n阶有向简单图，若D中每个顶点都邻接到其余的n-1个顶点，又邻接于其余的n-1个顶点，则称D是n阶有向完全图阶有向完全图。设D为n阶有向简单图，若D的基图为n阶无向完全图Kn，则称D是n阶竞赛图阶竞赛图。v在图9.4中，(1)为K5，(2)为3阶有向完全图，(3)为4阶竞赛图。图14.4易知，n阶无向完全图，n阶有向完全图，n阶竞赛图的边数分别为n(n-1)/2，n(n1)，n(n-1)/2.。2正则图正则图定义定义9.7设G为n阶无向简单图，若 vV(G)，均有d(v)=k，则称G为k-正则图正则图
23、。由定义可知，n阶零图是0-正则图，n阶无向完全图是(n-1)正则图，彼得松图是3-正则图。由握手定理可知，n阶k-正则图中，边数m=kn/2，因而当k为奇数时，n必为偶数。六子图与补图 定义定义9.8 设G=，G=为两个图(同为无向图或同为有向图)，若V V且E E，则称G是G的子图子图，G为G的母图母图，记作G G.又若VV或EE，则称G为G的真子图。若V=V，则称G为G的生成子图生成子图。设G=为一图，V1 V且V1，称以V1为顶点集，以G中两个端点都在V1中的边组成边集E1的图为G的V1导出的子图导出的子图，记作GV1.又设E1E且E1，称以E1为边集，以E1中边关联的顶点为顶点集V1
24、的图为G的E1导出的子图，记作GE1.例例93(1)画出4阶3条边的所有非同构的无向简单图。(2)画出3阶2条边的所有非同构的有向简单图。解解(1)由握手定理可知，所画的无向简单图各顶点度数之和为23=6，最大度小于或等于3。于是所求无向简单图的度数列应满足的条件是，将6分成4个非负整数，每个整数均大于或等于0且小于或等于3，并且奇数的个数为偶数。将这样的整数列排出来只有下面三种情况：(a)3，1，1，1(b)2，2，1，1(c)2，2，2，0将每种度数列所有非同构的图都画出来即得所要求的全部非同构的图，见图14.6中(1)，(2)，(3).(2)由握手定理可知，所画有向简单图各顶点度数之和为
25、4，最大出度和最大入度均小于或等于2.度数列及入度出度列为(a)1，2，1(b)2，2，0四个所要求的有向简单图见图14.6中(d)，(e)，(f)，(g).2补图与自补图定义定义9.9设G=为n阶无向简单图，以V为顶点集，以所有使G成为完全图Kn的添加边组成的集合为边集的图，称为G的补图，记做.若图G ，则称G是自补图。定义定义9.10 设G=为无向图。(1)设eE，从G中去掉边e，称为删除删除e，并用G-e表示从G中删除e所得子图。又设EE，从G中删除E中所有的边，称为删除删除E，并用G-E表示删除E后所得子图。(2)设vV，从G中去掉v及所关联地一切边称为删除顶删除顶点点v，并用G-v表
26、示删除v后所得子图。又设VV，称从G中删除V中所有顶点为删除删除V，并用G-V表示所得子图。(3)设边e=(u，v)E，先从G中删除e，然后将e的两个端点u，v用一个新的顶点w(或用u或v充当w)代替，使w关联除e外u，v关联的一切边，称为收缩边收缩边e，并用Ge表示所得新图。(4)设u，vV(u，v可能相邻，也可能不相邻，且uv)，在u，v之间加新边(u，v)，称为加新边加新边，并用G(u，v)(或G(u，v)表示所得新图。9.2通路与回路一通路与回路的定义定义定义9.11 设G为无向标定图，G中顶点与边的交替序列=称为到的通路通路，其中，为的端点，r=1，2，l，分别称为的始点与终点，中边
27、的条数称为它的长度。若，则称通路为回路回路。若的所有边各异，则称为简简单通路单通路，又若，则称为简单回路简单回路。若的所有顶点(除与可能相同外)各异，所有边也各异，则称为初级通路初级通路或路径路径，此时又若，则称为初级回路初级回路或圈圈。将长度为奇数的圈称为奇圈奇圈，长度为偶数的圈称为偶圈偶圈。，注意，在初级通路与初级回路的定义中，仍将初级回路看成初级通路(路径)的特殊情况，只是在应用中初级通路(路径)都是始点与终点不相同的，长为1的圈只能由环生成，长为2的圈只能由平行边生成，因而在简单无向图中，圈的长度至少为3.另外，若中有边重复出现，则称为复杂通路复杂通路，又若，则称为复杂回路。复杂回路。
28、在有向图中，通路、回路及分类的定义与无向图中非常相似，只是要注意有向边方向的一致性。在以上的定义中，将回路定义成通路的特殊情况，即回路也是通路，又初级通路(回路)是简单通路(回路)，但反之不真。用顶点与边的交替序列定义了通路与回路，但还可以用更简单的表示法表示通路与回路。(1)只用边的序列表示通路(回路)。定义14.11中的可以表示成(2)在简单图中也可以只用顶点序列表示通路(回路)。定义中的也可以表示成.(3)为了写出非标定图中的通路(回路)，可以先将非标定图标成标定图，再写出通路与回路。(4)在非简单标定图中，当只用顶点序列表示不出某些通路(回路)时，可在顶点序列中加入一些边(这些边是平行
29、边或环)，可称这种表示法为混合表示法混合表示法。二.n阶图中通路与回路的性质定理定理9.5在n阶图G中，若从顶点vi到vj（vivj）存在通路，则从vi到vj存在长度小于或等于（n-1）的通路。推论推论在n阶图G中，若从顶点vi到vj（vivj）存在通路，则vi到vj一定存在长度小于或等于n-1的初级通路（路径）。定理定理9.6在一个n阶图G中，若存在vi到自身的回路，则一定存在vi到自身长度小于或等于n的回路。推论推论在一个n阶图G中，若存在vi到自身的简单回路，则一定存在vi到自身长度小于或等于n的初级回路。例例9.5(1)无向完全图Kn（n3）中有几种非同构的圈？(2)无向完全图K3的顶
30、点依次标定为a,b,c.在定义意义下K3中有多少个不同的圈？解解(1)长度相同的圈都是同构的，因而只有长度不同的圈才是非同构的，易知Kn（n3）中含长度为3，4，n的圈，所以Kn（n3）中有n-2种非同构的圈。(2)在同构意义下，K3中只有一个长度为3的圈。但在定义意义下，不同起点（终点）的圈是不同的，顶点间排列顺序不同的圈也看成是不同的，因而K3中有6个不同的长为3的圈：abca,acba,bacb,bcab,cabc,cbac。如果只考虑起点（终点）的差异，而不考虑顺时针逆时针的差异，应有3种不同的圈，当然它们都是同构的，画出图来只有一个。9.3图的连通性一、无向图的连通性v定义定义9.1
31、2设无向图G=,u,vV，若u,v之间存在通路，则称u,v是连通的是连通的，记作uv.vV，规定vv.v由定义不难看出，无向图中顶点之间的连通关系v=（u,v）|u,vV且u与v之间有通路v是自反的，对称的，传递的，因而是V上的等价关系。v定义定义9.13若无向图G是平凡图或G中任何两个顶点都是连通的，则称G为连通图连通图，否则称G是非连通非连通图图或分离图分离图。v易知，完全图Kn(n1)都是连通图，而零图Nn(n2)都是分离图。v定义定义9.14设无向图G=，V关于顶点之间的连通关系的商集V/=V1,V2,Vk，Vi为等价类，称导出子图GVi(i=1,2,k)为G的连通分支连通分支，连通分
32、支数k常记为p(G).v由定义可知，若G为连通图，则p(G)=1，若G为非连通图，则p(G)2，在所有的n阶无向图中，n阶零图是连通分支最多的，p(Nn)=n.二、无向图中顶点之间的线程线及距离二、无向图中顶点之间的线程线及距离v定义定义9.15设u,v为无向图G中任意两个顶点，若uv，称u,v之间长度最短的通路为u,v之间的短程线短程线，短程线的长度称为u,v之间的距离距离，记作d(u,v).当u,v不连通时，规定d(u,v)=.距离有以下性质：v1d(u,v)0，u=v时，等号成立。2具有对称性，d(u,v)=d(v,u).3满足三角不等式：u,v,wV(G)，则d(u,v)+d(v,w)
33、d(u,w)v在完全图Kn(n2)中，任何两个顶点之间的距离都是1，而在n阶零图Nn(n2)中，任何两个顶点之间的距离都为.三、无向图的连通度定义定义9.16设无向图G=，若存在VV，且V，使得p(G-V)p(G)，而对于任意的VV，均有p(G-V)=p(G)，则称V是G的点点割集割集，若V是单元集，即V=v，则称v为割割点点。见教材P159，在图9.8中，v2,v4，v3，v5都是点割集，而v3,v5都是割点。注意，v1与悬挂顶点v6不在任何割集中。定义定义9.17设无向图G=，若存在EE，且E，使得p(G-E)p(G)，而对于任意的EE，均有p(G-E)=p(G)，则称E是G的边割集边割集
34、，或简称为割集。若E是单元集，即E=e，则称e为割边割边或桥桥。在图9.8中，e6,e5,e2,e3,e1,e2,e3,e4,e1,e4,e1,e3,e2,e4都是割集，其中e6,e5是桥。v定义定义9.18设G为无向连通图且为非完全图，则称(G)=min|V|V为G的点割集v为G的点连通度点连通度，简称连通度连通度。规定完全图Kn(n1)的点连通度为n-1，又规定非连通图的点连通度为0.又若(G)k，则称G是k-连通图连通图，k为非负整数。(G)有时简记为.图14.8中图的点连通度为1，此图为1-连通图。K5的点连通度=4，所以K5是1-连通图，2-连通图，3-连通图，4-连通图。图9.7中
35、，（1）图的点连通度=2，所以它是1-连通图，也是2-连通图。若G是k-连通图（k1）则在G中删除任何k-1个顶点后，所得图一定还是连通的。v定义定义9.19设G是无向连通图，称v(G)=min|E|E是G的点割集v为G的边连通度边连通度。规定非连通图的边连通度为0.又若(G)r，则称G是r边边-连通图连通图。若G是r边-连通图，则在G中任意删除r-1条边后，所得图依然是连通的。完全图Kn的边连通度为n-1，因而Kn是r边-连通图，0rn-1.图14.8中图的边连通度=1，它只能是1边-连通图。(G)也可以简记为.v设G1,G2都是n阶无向简单图，若(G1)(G2)，则称G1比G2的点连通程度
36、高。若(G1)(G2)，则称G1比G2的边连通程度高。v定义定义9.20设D=为一个有向图。vi,vjV，若从vi到vj存在通路，则称vi可达可达vj，记作vivj，规定vi总是可达自身的，即vivi.若vivj且vjvi，则称vi与vj是相互可相互可达达的，记作vivj.规定vivi.v与都是V上的二元关系，并且不难看出是V上的等价关系。v定义定义9.21设D=为有向图，vi,vjV，若vivj，称vi到vj长度最短的通路为vi到vj的短程线短程线，短程线的长度为vi到vj的距离，记作d.v与无向图中顶点vi与vj之间的距离d(vi,vj)相比，d除无对称性外，具有d(vi,vj)所具有的一
37、切性质。定义定义9.22设D=为一个有向图。若D的基图是连通图，则称D是弱连通图弱连通图，简称为连通连通图图。若vi,vjV，vivj与vjvi至少成立其一，则称D是单向连通图单向连通图。若均有vivj，则称D是强连通图强连通图。见教材P161，在图9.11中，（1）为强连通图，（2）为单连通图，（3）是弱连通图。由定义可知，强连通图一定是单向连通图，单向连通图一定是弱连通图。定理定理9.8设有向图D=，D=v1,v2,vn.D是强连通图当且仅当D中存在经过每个顶点至少一次的回路。定理定理9.9设D是n阶有向图，D是单向连通图当且仅当D中存在经过每个顶点至少一次的通路。五、扩大路径法及极大路径
38、设G=为n阶无向图，E，设I为G中一条路径，若此路径的始点或终点与通路外的顶点相邻，就将它们扩到通路中来，继续这一过程，直到最后得到的通路的两个端点不与通路外的顶点相邻为止，设最后得到的通路的两个端点不与通路外的顶点相邻为止，设最后得到的路径为l+k（长度为l的路径扩大成了长度为l+k的路径），称l+k为“极大路径极大路径”，称使用此种方法证明问题的方法为“扩扩大路径法大路径法”。（演示）六、二部图及判别定理v定义定义14.23设G=为一个无向图，若能将V分成V1和V2（V1V2=V,V1V2=），使得G中的每条边的两个端点都是一个属于V1，另一个属于V2，则称G为二部图二部图（或称二分图，偶
39、图等），称V1和V2为互补顶点子集，常将二部图G记为.又若G是简单二部图，V1中每个顶点均与V2中所有顶点相邻，则称G为完全二部图完全二部图，记为Kr,s，其中r=|V1|,s=|V2|.v注意，n阶零图为二部图。v在图14.13中所示各图都是二部图，其中，(1)，(2)，(3)为K6的子图，(3)为完全二部图K3,3，常将K3,3画成与其同构的(5)的形式，K3,3是下文中经常遇到的图。(4)是K5的子图，它是完全二部图K2,3，K2,3常画成(6)的形式。习题课主要内容：1、通路与回路的定义。2、n阶图中通路与回路的性质。学习要求：1.深刻理解通路与回路的定义及其分类。2.能正确地使用不同
40、的表示法表示通路与回路。3.理解同构意义下与定义意义下通路与回路的区别与联系。4.深刻理解无向图中两个顶点之间的连通关系、短程线、距离、图的连通性等概念。5.深刻理解点割集、边割集、点连通度、边连通度等概念。6.理解有向图中，顶点之间的可达、相互可达关系、短程线、距离等概念。7.深刻理解有向图的连通性及分类，以及判别定理。1、设无向图G中只有两个奇度顶点u与v，试证明u与v必连通。用反证法。假设u与v不连通，即u与v之间无通路，则u与v处于G的不同连通分支中。不妨设u在G1，v在G2中。于是，G1与G2作为G的子图，他们中均只含有一个奇度顶点，这与握手定理的推论矛盾。2.设n阶无向简单图G有m
41、条边，已知m(n-1)(n-2)+1，证明G必连通。证明：（1）任何n阶简单图的边数m均小于等于完全图Kn的边数n(n-1)。（2）若G中无孤立点，则(G)1。用归纳法。n=1时，G为平凡图，显然G连通。n=2时，m(n-1)(n-2)+1=1，此时G为K2，当然连通。设n=k(k2)，m(k-1)(k-2)+1时结论成立，要证明当n=k+1,mk(k-1)+1时结论也成立。(i)若G为Kk+1，G当然连通。(ii)若G中含孤立点，一定推出矛盾。删去G中的孤立点，记作G1。则G1的边数mk(k-1)+1，这与G1为阶数小于等于k的简单图矛盾，故G中不可能含孤立点。(iii)由(i)、(ii)可
42、知，只需对G不为完全图、又不含孤立点的情况加以证明。G中存在v0，使1d(v0)k-1（G中无孤立点，又不是k+1阶完全图），令G=G-v0，则G为k阶简单图，且G的边数mk(k-1)+1-(k-1)=(k(k-1)-(k-1)+1=(k-1)(k-2)+1由归纳假设可知，G是连通图，而G为G的子图，故G也连通。3、设G为n阶无向简单图，证明以下题目：（1）当(G)时，证明G连通。证明（1）要用到n阶简单图的最大度最大度n-1。用反证法。假设G至少有两个连通分支，设G1,G2为其中的两个，并设G1,G2的阶数分别为n1和n2，则n1+n2n，minn1,n2。于是，对任意的vV(G1)，dG1
43、(V)=dG(V)-1，这与(G)矛盾，所以G连通。（2）当(G)(n+k-1)时，证明G是k-连通图。利用（1）的结果。要证明G是k-连通图，只需证明从G中删除任意（k-1）个顶点后，所得图依然连通。证明：设V为V(G)的任意子集，且|V|=k-1。令G=G-V，则G为n-(k-1)=n-k+1=n阶无向简单图，而(G)(G)-(k-1)(n+k-1)-(k-1)=(n+k-1-2k+2)=(n-k+1)=n由当(G)时，G连通可知，G连通，故G为k-连通图。9.4图的矩阵表示一、无向图与有向图的关联矩阵图可以用集合来定义，但多半用图形来表示，此外，还可以用矩阵来表示图。用矩阵表示图，便于用
44、代数方法研究图的性质，也便于计算机处理图。用矩阵表示图之前，必须将图的顶点或边标定顺序，使其成为标定图。本节中主要讨论无向图及有向图的关联矩阵及有向图的邻接矩阵和可达矩阵。定义定义14.24设无向图G=，V=v1,v2,vn，E=e1,e2,em，令mij为顶点vi与边ej的关联次数，则称(mij)nm为G的关联矩阵关联矩阵，记作M(G).图14.14所示无向图的关联矩阵为M(G)=不难看出，关联矩阵M(G)有以下性质：1Mij=2(j=1,2,m)即M(G)每列元素之和均为2，这正说明每条边关联两个顶点（环所关联的两个端点重合）。2Mij=d(vi)，即M(G)第i行元素之和为vi的度数，i
45、=1,2,n.3d(vi)=mij=mij=2=2m,这个结果正是握手定理的内容，即各顶点的度数之和等于边数的2倍。4第j列与第k行相同，当且仅当边ej与ek是平行边。5Mij=0当且仅当vi是孤立点。v定义定义14.25设有向图D=中无环，V=v1,v2,vn，E=e1,e2,em,令mij=v则称(mij)nm为D的关联矩阵关联矩阵，记作M(D).v图14.15所示图D的关联矩阵为M(D)=图14.15M(D)有如下各条性质：1mij=0，j=1,2,m，从而mij=0，这说明M(D)中所有元素之和为0.2M(D)中，负1的个数等于正1的个数，都等于边数m，这正是有向图握手定理的内容。3第
46、i行中，正1的个数等于d+(vi)，负1的个数等于d-(vi).4平行边所对应的列相同。二、有向图的邻接矩阵定义定义14.26设有向图D=，V=v1,v2,vn，E=e1,e2,，em，令aij(1)为顶点vi邻接到顶点vj边的条数，称(aij(1)nn为D的邻接矩阵邻接矩阵，记作A(D)，或简记为A.图14.16所示有向图D的邻接矩阵为A=图14.16=有向图的邻接矩阵有以下性质。1aij(1)=d+(vi),i=1,2,n，于是，aij(1)=d+(vi)=m，类似地，aij(1)=d(vj),j=1,2,n，而aij(1)=d-1(vj)=m.这也正反映了有向图握手定理的内容。2由1不难
47、看出，A(D)中所有元素之和为D中长度为1的通路中，而aij(1)为D中长度为1的回路（环）的个数。现在要讨论的问题是，如何利用A(D)计算出D中长度为l的通路数和回路数。在这里通路是定义意义下的概念，不同起点的通路都看成是不同的，并且回路看成是通路的特殊情况。为了解决提出的问题，要计算A(D)的幂，把l次幂记作Al(D)或简记作Al.设Al=(aij(l)nn(l2)，其中元素aij(l)=aik(l-1)akj(1)，则aij(l)为顶点vi到vj长度为l的通路数，当i=j时，即aij(l)(Al的主对角线上的元素)为vi到vi长度为l的回路数（这里的回路可以是初级的，可以是简单的，也可以
48、是复杂的）。而aij(l)为D中长度为l的通路总数，其中，aij(l)为D中的长度为l的回路总数。从以上分析可得出下面定理和推论。=定理定理14.11设A为有向图D的邻接矩阵，V=v1,v2,vn为D的顶点集，则A的l次幂Al（l1）中元素aij(l)为D中vi到vj长度为l的通路数，其中aii(l)为vi到自身长度为l的回路数，而aij(l)为D中长度为l的通路总数，其中aii(l)为D中长度为l的回路总数。推论推论设Bl=A+A2+Al（l1），则Bl中元素bij(l)为D中长度小于或等于l的通路数，其中bii(l)为D中长度小于或等于l的回路数。前面已经计算出图14.16所示有向图D的邻接矩阵A，下面给出A2，A3，A4.A2=A3=A4=从A1A4不难看出，D中v2到v4的长度为1,2,3,4的通路分别为0，1，1，2条。v4到自身长度为1，2，3，4的回路分别为1，2，3，5条，其中有复杂回路。D中长度小于或等于4的通路有53条，其中有15条为回路。三、有向图的可达矩阵v定义定义14.27设D=为有向图。V=v1,v2,vn，令pij=称(pij)nn为D的可达矩阵可达矩阵，记作P(D)，简记为P.由于viV，vivi，所以P(D)主对角线上的元素全为1.v 2 MR 2 ,Anv A2 v v -1 0 n ,