《无向图及有向图》PPT课件.ppt

,第一讲无向图及有向图,知识结构图的定义图的一些概念和规定简单图和多重图顶点的度数与握手定理图的同构子图与补图,引例1：哥尼斯堡七桥问题（图论应用的开始）,问：能否从某地出发，通过每桥恰好一次，走遍了七桥后又返回到原处？瑞士数学家欧拉在1736年发表了一篇论文讨论这个问题，指出这个问题无解。,普雷格尔河,欧拉：传奇的一生,年少时，听从父亲的安排，巴塞尔大学，学习神学和希伯来语，结果被约翰伯努利欣赏，17岁获得硕士学位之后，才开始专供数学。为获得圣彼得堡科学院的医学部的职位空缺，欧拉在巴塞尔便全力投入生理学的研究，并出席医学报告会。1727年，等他到达俄罗斯时，叶卡捷琳娜一世女皇去世，他进入数学部。1733年，欧拉回到瑞士，并结婚，一生共生育13个孩子，5个存活。为了赢得巴黎奖金而投身于一个天文学问题，那是几个有影响的大数学家搞了几个月时间的，欧拉在三天之后把它解决了。可是过分的劳累使他得了一场病，病中右眼失明了。欧拉到底出了多少著作，直至1936年人们也没有确切的了解。但据估计，要出版已经搜集到的欧拉著作，将需用大4开本60至80卷。彼得堡学院为了整理他的著作整整花了47年。,问题2(哈密顿环球旅行问题，1857年):十二面体的20个顶点代表世界上20个城市，能否从某个城市出发在十二面体上依次经过每个城市恰好一次最后回到出发点？,问题3(四色问题):对任何一张地图进行着色，两个共同边界的国家染不同的颜色，则只需要四种颜色就够了.,问题4(关键路径问题):一项工程任务,大到建造一座大坝,一座体育中心,小至组装一台机床,一架电视机,都要包括许多工序.这些工序相互约束,只有在某些工序完成之后,一个工序才能开始.即它们之间存在完成的先后次序关系,一般认为这些关系是预知的,而且也能够预计完成每个工序所需要的时间.这时工程领导人员迫切希望了解最少需要多少时间才能够完成整个工程项目,影响工程进度的要害工序是哪几个？,二、图的概念,设A，B为任意的两个集合，a,b|aAbB为A与B的无序积，记作A&B。可将无序积中的无序对a,b记为(a,b)，并且允许ab。无论a,b是否相等，均有(a,b)(b,a)，故A&BB&A。元素可以重复出现的集合称为多重集合或者多重集。例如多重集合a,a,b,b,b,c,d,(a,a),(b,b),(b,b).,定义1一个无向图（undirectedgraph）是一个有序的二元组,记作G，其中（1）V称为顶点集，其元素称为顶点或结点（vertices,nodes）。（2）E称为边集，它是无序积V&V的多重子集，其元素称为无向边，简称边（edges）。,例1(1)给定无向图G，其中Vv1,v2,v3,v4,v5，E=(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5).,例1（2）E,定义2一个有向图（directedgraph）是一个有序的二元组，记作D，其中（1）V称为顶点集，其元素称为顶点或结点。（2）E为边集，它是笛卡儿积VV的多重子集，其元素称为有向边，简称边。,图的一些概念和规定,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为平凡图(trivialgraph)。,关联与关联次数、环、孤立点,设G为无向图，ek(vi,vj)E，称vi,vj为ek的端点，ek与vi或ek与vj是彼此相关联的。若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中的环。无论在无向图中还是在有向图中，无边关联的顶点均称为孤立点(isolatedvertices)。,相邻与邻接,设无向图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相邻(adjacent)。,vi,vj,ek,el,vi,vj,ek,el,简单图与多重图,定义3在无向图中，关联一对顶点的无向边如果多于1条，则称这些边为平行边，平行边的条数称为重数。在有向图中，关联一对顶点的有向边如果多于1条，并且这些边的始点和终点相同(也就是它们的方向相同)，则称这些边为平行边(paralleledges)。含平行边的图称为多重图(multigraph)。既不含平行边也不含环的图称为简单图(simplegraph)。例如：在图中e5与e6是平行边，不是简单图。,顶点的度数(degree),定义4设G为一无向图，vV，称v作为边的端点次数之和为v的度数，简称为度，记做dG(v)。在不发生混淆时，简记为d(v)。设D为有向图，vV，称v作为边的始点次数之和为v的出度(out-degree)，记做d+D(v)，简记作d+(v)。称v作为边的终点次数之和为v的入度(in-degree)，记做d-D(v)，简记作d-(v)。称d+(v)+d-(v)为v的度数，记做d(v)。,设G为一个n阶无向图，Vv1,v2,vn，称d(v1)，d(v2)，d(vn)为G的度数列。对于顶点标定的无向图，它的度数列是唯一的。类似地，设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,图的度数的相关概念,在无向图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的顶点为悬挂顶点，与它关联的边称为悬挂边。度为偶数(奇数)的顶点称为偶度(奇度)顶点。,图的度数举例,d(v1)4(注意，环提供2度)，4，1，v4是悬挂顶点，e7是悬挂边。,d+(a)4，d-(a)1+4+0-3-1,度数列：4、4、2、1、3,出：4、0、2、1入：1、3、1、2,边：7,度数列：5、3、3、3边数：7,握手定理(TheHandshakingTheorem),定理1设G为任意无向图，Vv1,v2,vn，|E|m，则,说明任何无向图中，各顶点度数之和等于边数的两倍。证明G中每条边(包括环)均有两个端点，所以在计算G中各顶点度数之和时，每条边均提供2度，当然，m条边，共提供2m度。,定理2设D为任意有向图，Vv1,v2,vn，|E|m，则,推论,推论任何图(无向或有向)中，奇度顶点的个数是偶数。证明设G为任意一图，令V1v|vVd(v)为奇数V2v|vVd(v)为偶数则V1V2V，V1V2，由握手定理可知,由于2m和,，所以,为偶数，,但因V1中顶点度数为奇数，,所以|V1|必为偶数。,例：(3,3,2,1)，(3,2,2,1,1)(3,3,2,2)、(3,2,2,2,1)是否可图化？解：(3,3,2,1)，(3,2,2,1,1)不可以图化(3,3,2,2)可以图化(3,2,2,2,1)可以图化,若非负整数列可以对应为图的度数列，则称之为可图化。,定理4设G为任意n阶无向简单图，则(G)n-1。证明因为G既无平行边也无环，所以G中任何顶点v至多与其余的n-1个顶点均相邻，于是d(v)n-1，由于v的任意性，所以(G)n-1。例2判断下列各非负整数列哪些可图化的？哪些可简单图化的？(1)(5,5,4,4,2,1)不可图化。(2)(5,4,3,2,2)可图化，不可简单图化。若它可简单图化，设所得图为G，则(G)max5,4,3,2,25，这与定理矛盾,(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之一相邻，去掉v4后，与v4关联的边也去掉，于是剩余的v1，v2，v3组成的图的度数应该是2、3、3，此时因为最大度为3，不满足n-1=2的要求，因此这三个点构成的图必定有平行边或者环，不是简单图，此时若加入v4及与v4关联的边构成的图必定也不是简单图。即有(3)中序列也不可简单图化。,(5)(4,4,3,3,2,2)可简单图化。下图中两个6阶无向简单图都以(5)中序列为度数列。,定义5设G1，G2为两个无向图，若存在双射函数f：V1V2，对于vi,vjV1，(vi,vj)E1当且仅当(f(vi),f(vj)E2，并且(vi,vj)与(f(vi),f(vj)的重数相同，则称G1与G2是同构的(isomorphic)，记做G1G2。说明(1)点数、边数和度数列对影响等。(2)在图同构的意义下，图的数学定义与图形表示是一一对应的。,方法一：边伸缩,方法二：点挪动,a,b,c,d,a,b,c,d,a,b,e,d,c,e,a,d,c,b,e1,e1,e2,e2,完全图(completegraph),定义6设G为n阶无向简单图，若G中每个顶点均与其余的n-1个顶点相邻，则称G为n阶无向完全图，简称n阶完全图，记做Kn(n1)。设D为n阶有向简单图，若D中任意两个不同的顶点之间都存在两条方向相反的边，则称D是n阶有向完全图。,n阶无向完全图的边数为：n(n-1)/2n阶有向完全图的边数为：n(n-1),完全图举例,K5,3阶有向完全图,4阶竞赛图,子图(subgraph),定义8设G，G为两个图(同为无向图或同为有向图)，若VV且EE，则称G是G的子图，G为G的母图，记作GG。若VV或EE，则称G为G的真子图。若VV，则称G为G的生成子图。设G为一图，V1V且V1，称以V1为顶点集，以G中两个端点都在V1中的边组成边集E1的图为G的V1导出的子图（inducedsubgraph），记作GV1。设E1E且E1，称以E1为边集，以E1中边关联的顶点为顶点集V1的图为G的E1导出的子图（inducedsubgraph），记作GE1。,点全选！,点不一定全选！,例：画出K4的所有非同构的生成子图。解:K4的所有非同构的生成子图如图所示,导出子图举例,在上图中，设G为(1)中图所表示，取V1a,b,c，则V1的导出子图GV1为(2)中图所示。取E1e1,e3，则E1的导出子图GE1为(3)中图所示。,例3画出4阶3条边的所有非同构的无向简单图。由握手定理可知，所画的无向简单图各顶点度数之和为236，最大度小于或等于3。于是所求无向简单图的度数列应满足的条件是，将6分成4个非负整数，每个整数均大于或等于0且小于或等于3，并且奇数的个数为偶数。将这样的整数列排出来只有下面三种情况：,(1)2，2，1，1(2)3，1，1，1(3)2，2，2，0,将每种度数列所有非同构的图都画出来即得所要求的全部非同构的图。,定义9设G为n阶无向简单图，以V为顶点集，以所有使G成为完全图Kn的添加边组成的集合为边集的图，称为G的补图(complementarygraph)，记作G。若图GG，则称为G是自补图。,(1)为自补图(2)和(3)互为补图,，显然(2)和(3)不同构,，不自补,课后作业题：,173页7.17.15其中选作的是：7.9、7.12、7.14、7.15其余的必做！,