第七章 图的基本概念.ppt

《第七章 图的基本概念.ppt》由会员分享，可在线阅读，更多相关《第七章 图的基本概念.ppt（104页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第7章章 图的基本概念图的基本概念 图论图论（graphictheory）的起源可追溯到18世纪，数学家欧拉1736年发表了关于图论的第一篇论文，解决了著名的哥尼斯堡七桥问题。但直到20世纪中后期，尤其是计算机科学与技术的发展，图的理论研究和应用研究才得到广泛的重视，图论作为一个重要的数学分支，才真正确立了自己的地位。图论的内容十分丰富,是一门交叉性很强、应用很广泛的学科。计算机科学、网络理论、信息论、运筹学、语言学、物理、化学等都以图作为工具,来解决理论问题和实际问题。离散数学研究的图是不同于几何图形、机械图形的另一种数学结构,不关心图中顶点的位置、边的长短和形状,只关心顶点与边的联结关系

2、。目录7.1无向图及有向图7.2通路、回路、图的连通性7.3图的矩阵表示7.4最短路径问题及关键路径7.1 无向图及有向图无向图及有向图设A,B为两集合,称a,baAbB为A与B的无序积,记作AB将无序对a,b记作(a,b).J定义7.1一个无向图G是一个二元组,即G,其中,(1)V是一个非空的集合,称为G的顶点集,V中元素称为顶点或结点；(2)E是无序积VV的一个多重子集,称E为G的边集,E中元素称为无向边或简称边.无向图元素可重复出现的集合为元素可重复出现的集合为多重集多重集例如：G=,V=v1,v2,v3,v4,v5,E=(v1,v2),(v2,v2),(v2,v3),(v1,v3),(

3、v1,v3),(v1,v4)G的图形为：e5v5v4v3v2v1e4e3e2e1e6有向图有向图J定义7.2一个有向图D是一个二元组,即D,其中,(1)V同无向图中的顶点集；(2)E是卡氏积的多重子集,其元素称为有向边,也简称边.有时用V(D),E(D)分别表示图D的顶点集和边集。例如：D=,V=v1,v2,v3,v4,v5,E=,G的图形为：e5v5v4v3v2v1e4e3e2e1e6e7e8设G为一无向图或有向图(1)若V,E都是有穷集合,则称G是有限图.(2)若Vn,则称G为n阶图(3)若E,则称G为零图特别是,若此时又有V1,则称G为平凡图.5阶图阶图零图零图平凡图平凡图J定义7.3设

4、ek(vi,vj)为无向图G中的一条边,称vi,vj为ek的端点,ek与vi(或vj)是彼此关联的.无边关联的顶点称为孤立点.若一条边所关联的两个顶点重合,则称此边为环.e5v5v4v3v2v1e4e3e2e1e6ek与vi(或vj)的关联次数1vi(vj)是ek的端点且vivj,2vi(vj)是ek的端点且vivj,0vi(vj)不是ek的端点e5v5v4v3v2v1e4e3e2e1e6J定义7.4设无向图G=,vi,vjV,ek,elE.(1)若存在一条边e以vi、vj为端点,即e=(vi,vj),则称vi,vj是彼此相邻的,简称相邻的(2)若ek,el至少有一个公共端点,则称ek,el是

5、彼此相邻的,简称相邻的e5v5v4v3v2v1e4e3e2e1e6对有向图若ekvi,vj,除称vi,vj是ek的端点外,还称vi是ek的始点,vj是ek的终点,vi邻接到vj,vj邻接于vi.e5v5v4v3v2v1e4e3e2e1e6e7e8J定义7.5设G为一无向图,viV,称vi作为边的端点的次数之和为vi的度数,简称度,记作d(vi).称度数为1的顶点为悬挂顶点,它所对应的边为悬挂边.v1v2v5v4v3d(vi)=?设D为一有向图,vjV,称vj作为边的始点的次数之和,为vj的出度,记作d+(vj)；称vj作为边的终点的次数之和,为vj的入度,记作d-(vj)；称vj作为边的端点的

6、次数之和,为vj的度数,简称度,记作d(vj).显然d(vj)d+(vj)d-(vj).d(v1)3，d+(v1)2，d-(v1)1；d(v2)3，d+(v2)2，d-(v2)1；d(v3)5，d+(v3)2，d-(v3)3；d(v4)d+(v4)d-(v4)0；d(v5)1，d+(v5)0，d-(v5)1；其中，v5是悬挂结点，为悬挂边。?例v5v1v2v3v4对于图G,记(G)maxd(v)vV,(G)mind(v)vV,分别称为G的最大度和最小度.v1v2v5v4v34，0。若DV,E是有向图,除了(D),(D)外,还有最大出度、最大入度、最小出度、最小入度,分别定义为v5v4v3v2v

7、1J定理7.1（握手定理）设图G为无向图或有向图,Vv1,v2,.,vn,|E|=m(m为边数),则J推论任何图(无向的或有向的)中,度为奇数的顶点个数为偶数.J定理7.2设有向图D,Vv1,v2,.,vn,Em,则设Vv1,v2,.,vn为图G的顶点集,称(d(v1),d(v2),.,d(vn)为G的度数序列.?例v1v2v5v4v3度数序列（4，4，3，1，0）度数序列（3，4，3，4，2）v5v4v3v2v1(1)(3,3,2,3),(5,2,3,1,4)能成为图的度数序列吗？为什么？答：不能，由握手定理易知。(2)已知图G中有10条边,4个3度顶点,其余顶点的度数均小于等于2.问G中至

8、少有多少个顶点？为什么？答：至少有8个顶点。?例J定义7.6在无向图中,关联一对顶点的无向边如果多于1条,称这些边为平行边.平行边的条数称为重数.在有向图中,关联一对顶点的有向边如果多于1条,且它们的始点与终点相同,则称这些边为有向平行边,简称平行边.含平行边的图称为多重图.既不含平行边,也不含环的图称为简单图.e5v5v4v3v2v1e4e3e2e1e6e4与e5是平行边e3与e4是平行边e7与e8不是平行边e5v5v4v3v2v1e4e3e2e1e6e7e8J定义7.7设G=是n阶无向简单图,若G中任何顶点都与其余的n-1个顶点相邻,则称G为n阶无向完全图,记作Kn.设D=为n阶有向简单图

9、,若对于任意的顶点u,vV(uv),既有有向边,又有,则称D是n阶有向完全图.注：Kn均指无向完全图.图(1)中所示为K4,(2)所示为K5,(3)所示为3阶有向完全图.?例(1)(2)(3)J定义7.8设G=,G=是两个图.若VV,且EE,则称G是G的子图,G是G的母图,记做GG.若GG且GG(即VV或EE),则G是G的真子图.若GG且V=V则称G是G的生成子图.设V1V,且V1,以V1为顶点集,以两端点均在V1中的全体边为边集的G的子图,称为V1导出的导出子图.设E1E,且E1,以E1为边集,以E1中关联的顶点的全体为顶点集的G的子图称为E1导出的导出子图.?例下图给出了图G以及它的真子图

10、G和生成子图G。G是结点集v1,v2,v4,v5,v6的导出子图。v1v2v3v4e4e5e1e2e3v1v2v3v4e4e1e3v1v2e4e5v1 v2v3e4e1e2e3v1 v2v3e1e3v1v2e1?例(1)(2)(3)(6)(5)(4)J定义7.9设G=是n阶无向简单图.以V为顶点集,以所有能使G成为完全图Kn的添加边组成的集合为边集的图,称为G相对于完全图Kn的补图,简称G的补图,记作G.有向简单图的补图可类似定义.?例互补互补互补互补观察下列图有何特点？J图(a)、图(b)、图(c)和图(d)所表示的图形实际上都是一样的。bdcdcbadcbadcbaa图(a)图(b)图(c

11、)图(d)J定义7.10设两个无向图G1=,G2=,如果存在双射函数：V1V2,使得对于任意的e=(vi,vj)E1当且仅当e=(vi),(vj)E2,并且e与e的重数相同,则称G1与G2是同构的,记作G1G2.(1)(2),顶点之间的对应关系为av1,bv2,cv3,dv4,ev5.(a)(b)(c)(a)所示图称为彼德森图.(a)(b)(c)1、顶点个数相同2、边的条数相同3、度数相同的结点数相同两图同构?例(1)画出4个顶点3条边的所有可能非同构的无向简单图；(1)(2)(3)(2)画出3个顶点2条边的所有可能非同构的有向简单图.(1)(2)(3)(4)7.2 通路、回路、图的连通性通路

12、、回路、图的连通性J定义7.11给定图G.设G中顶点和边的交替序列为v0e1v1e2elvl,若满足如下条件:vi-1和vi是ei的端点(在G是有向图时,要求vi-1是ei的始点,vi是ei的终点),i1,2,l,则称为顶点v0到vl的通路.v0和vl分别称为此通路的起点和终点,中边的数目l称为的长度.当v0vl时,此通路称为回路.若中的所有边e1,e2,el互不相同,则称为简单通路或一条迹.若回路中的所有边互不相同,称此回路为简单回路或一条闭迹.若通路的所有顶点v0,v1,vl互不相同(从而所有边互不相同),则称此通路为初级通路或一条路径.若回路中,除v0vl外,其余顶点各不相同,所有边也各

13、不相同,则称此回路为初级回路或圈.有边重复出现的通路称为复杂通路,有边重复出现的回路称为复杂回路.由定义可知,初级通路(回路)是简单通路(回路),但反之不真.注：上述定义既适合无向图，也适合有向图。?例v1v0v4v2v3v5v8v6v7v1v0v4v2v3v1v0v4v2v3v1v0v4v2v3v5v8v6v7(1)为v0到v4的长为4的初级通路(2)为v0到v4的长为4的初级通路(3)为v0到v8的长为8的简单通路(4)为v0到v8的长为8的简单通路J定理7.3在一个n阶图中,若从顶点vi到vj(vivj)存在通路,则从vi到vj存在长度小于等于n-1的通路.推论在一个n阶图中,若从顶点v

14、i到vj(vivj)存在通路,则从vi到vj存在长度小于等于n-1的初级通路.J定理7.4在一个n阶图中,如果存在vi到自身的回路,则从vi到自身存在长度小于等于n的回路.推论在一个n阶图中,如果vi到自身存在一条简单回路,则从vi到自身存在长度小于等于n的初级回路.J定义7.12在一个无向图G中,若从顶点vi到vj存在通路(当然从vj到vi也存在通路),则称vi与vj是连通的.规定vi到自身总是连通的.在一个有向图D中,若从顶点vi到vj存在通路,则称vi可达vj.规定vi到自身总是可达的.短程线(无向图)设vi,vj为无向图G中的任意两点,若vi与vj是连通的,则称vi与vj之间长度最短的

15、通路为vi与vj之间的短程线,短程线的长度称为vi与vj之间的距离,记作d(vi,vj).短程线(有向图)设vi,vj为有向图D中任意两点,若vi可达vj,则称从vi到vj长度最短的通路为vi到vj的短程线,短程线的长度称为vi到vj的距离,记作d.性质u若vi不可达vj,规定d.d具有下面性质:(1)d0,当vivj时,等号成立.(2)满足三角不等式,即d+dd.在无向图中,还有对称性,即d(vi,vj)d(vj,vi).连通图(无向图)J定义7.13若无向图G是平凡图,或G中任意两顶点都是连通的,则称G是连通图;否则,称G是非连通图.无向图中,顶点之间的连通关系是等价关系.设G为一个无向图

16、,R是G中顶点之间的连通关系,按着R可将V(G)划分成k(k1)个等价类,记成V1,V2,Vk,由它们导出的导出子图GV1,GV2,GVk称为G的连通分支,其个数记为p(G).G1是连通图，p(G1)1；G2是非连通图，且p(G2)3。G1G2?例连通图(有向图)J定义7.14设D是一个有向图,如果略去D中各有向边的方向后所得无向图G是连通图,则称D是连通图,或称D是弱连通图.若D中任意两顶点至少一个可达另一个,则称D是单向连通图.若D中任何一对顶点都是相互可达的,则称D是强连通图?例图a为弱连通图；图b为单向连通图；图c为强连通图。图a图b图cJ定义7.15设无向图G,若存在顶点子集VV,使

17、G删除V将V中顶点及其关联的边都删除)后,所得子图GV的连通分支数与G的连通分支数满足p(G-V)p(G),而删除V的任何真子集V后,p(G-V)p(G),则称V为G的一个点割集.若点割集中只有一个顶点v,则称v为割点.若存在边集子集EE,使G删除E(将E中的边从G中全删除)后,所得子图的连通分支数与G的连通分支数满足p(G-E)p(G),而删除E的任何真子集E后,p(G-E)p(G),则称E是G的一个边割集.若边割集中只有一条边e,则称e为割边或桥.v2,v7，v3，v4为点割集，v3，v4为割点e1,e2，e1,e3,e4，e6，e7,e8，e2,e3,e4等都是割集，其中e6是桥。v5e

18、8v6v7v1v4v2v3e1e2e3e4e5e6e7e9?例本节概念:无向图、有向图、n阶图、零图、平凡图、彼此关联、相邻、度d(vi)、出度d+(vj)、入度d-(vj)、握手定理及其推论、度数序列、简单图、n阶无向完全图、子图、母图、生成子图、导出子图、补图、同构、通路、回路、连通图、点割集、边割集7.3图的矩阵表示1.无向图的关联矩阵2.有向图的关联矩阵3.有向图的邻接矩阵4.有向图的可达矩阵无向图的关联矩阵设无向图G,Vv1,v2,vn,Ee1,e2,em,令mij为顶点vi与边ej的关联次数,则称(mij)nm为G的关联矩阵,记为M(G)mij0 (v0 (vi i与与e ej j

19、无关无关),),1 (v1 (vi i与与e ej j关联关联1 1次次),),2 2 (v(vi i与与e ej j关联关联2 2次次,3 3 即即e ej j是以是以v vi i为端点的环为端点的环)?例e2v4v2v3v1e3e4e1e5关联矩阵M(G)的性质有向图的关联矩阵要求有向图D中无环存在.设D,Vv1,v2,vn,Ee1,e2,em,令则称(mij)nm为D的关联矩阵，记作M(D).v4v3v2v1e1e2e3e4e5?例关联矩阵M(D)的性质有向图的邻接矩阵设有向图D.V=v1,v2,vn,|E|m.令aij(1)为vi邻接到邻接到vj的边的条数,称(aij(1)mn为D的邻

20、接矩阵,记作A(D).v4v3v2v1?例邻接矩阵A(D)的性质(3)为D中边的总数,也可看成D中长度为1的通路总数,而为D中环的个数,即D中长度为1的回路总数.考虑Al(D)(简记Al),=这里Al=()nn(l2),则为顶点vi到vj长度为l的通路数,为它到自身长度为l的回路数.Al中所有元素之和为D中长度为l的通路数,而Al中对角线上元素之和为D中始于(终于)各顶点的长度为l的回路数.在图中,计算A2,A3,A4如下:v4v3v2v1J定理7.5设A为有向图D的邻接矩阵,V=v1,v2,vn,则Al(l1)中元素为vi到vj长度为l的通路数,为D中长度为l的通路总数,其中为D中长度为l的

21、回路数.J推论设Br=A+A2+Ar(r1),则Br中元素为D中vi到vj长度小于等于r的通路数,为D中长度小于等于r的通路总数,其中为D中长度小于等于r的回路总数.若再令矩阵B1=A,B2=A+A2,Br=A+A2+Ar,有向图的可达矩阵设D=为一有向,V=v1,v2,vn,令pii=1,i=1,2,n.称(pij)nn为D的可达矩阵,记作P(D),简记P.v4v3v2v1P=?例P中元素可如下确定:于是由D的邻接矩阵可求可达矩阵.7.4最短路径及关键路径1.最短路径问题2.关键路径问题权、带权图对于有向图或无向图G的每条边附加一个实数w(e)，则称w(e)为边e上的权.G连同附加在各边上的

22、实数称为带权图.常记带权图为G=.设G1是带权图G的子图,称为G1的权,记作W(G1).当然,W(G)是G的权.当无向边e=(vi,vj)或有向边e=时,w(e)也记为wij.E(G1)1.最短路径问题设带权图G=.G中每条边带的权均大于等于0.u,v为G中任意两个顶点,从u到v的所有通路中带权最小的通路称为u到v的最短路径.n设G=是n阶简单带权图,wij0.若顶点vi与vj不相邻,令wij=.求G中顶点v1到其余各顶点的最短路径.路径长度的的具体含义取决于边上权值所代表的意义。【例】交通网络中的带权图求最短路径的问题。（1）两地之间是否有路相通?（2）在有多条通路的情况下，哪一条最短?其中

23、，交通网络可以用带权图表示：图中顶点表示城镇，边表示两个城镇之间的道路，边上的权值可表示两城镇间的距离，交通费用或途中所需的时间等等。(1)设为顶点v1到顶点vi最短路径的权,若顶点vi获得了标号,称vi在第r步获得了p标号(永久性标号),其中,r0.(2)设为v1到vj的最短路径权的上界,若vj获得,在第r步获得t标号(临时性标号),r0.若干定义：(3)设Pr=v|v已获得p标号为第r步通过集,r0.(4)设Tr=V-Pr为第r步未通过集,r0.Dijkstra(标号法）的算法：开始,r0,v1获p标号:=0,P0=v1,T0=V-v1.vj(j1)的t标号:=w1j.求下一个p标号顶点.

24、设,将标在相应顶点vi处,表明vi获得p标号.修改通过集和未通过集:Pr=Pr-1vi,Tr=Tr-1-vi.,查Tr:若Tr=,则算法结束,否则转.修改Tr中各顶点的t标号:是刚刚获得标号顶点的p标号.令rr+1,转.求图中顶点v0与v5的最短路径.?例解:可以将计算过程用一张表表示出来(见下页表)31v5v3v2v154712v02v4631v5v3v2v154712v0 2v46viKv0v1v2v3v4v5012345011/v0433/v18877/v4644/v21099/v3013749由表可知,v5与v3相邻,v3与v4相邻,v4与v2相邻,v2与v1相邻,v1与v0相邻.这样

25、从v5往前追踪,得v0到v5的最短路径为=v0v1v2v4v3v5.W()=9.31v5v3v2v154712v02v46设D=为一个有向图,vV,称为v的后继元集;为v的先驱元集.2.关键路径问题（1）PERT图（计划评审技术图）设D=是n阶有向带权图,满足:1)D是简单图;2)D中无回路;3)有一个顶点入度为0,称此顶点为发点;有一个顶点出度为0,称此顶点为收点;4)记边带的权为wij;它常表示时间;则称D为PERT图.通常把计划、施工过程、生产流程、程序流程的都当成一个工程。除了很小的工程外、一般都把工程分为若干个叫做“活动”的子工程。完成了这些“活动”的子工程，这个工程就可以完成了。通

26、常我们用有向图表示一个工程。在这种有向图中，用顶点表示活动，用有向边表示活动vi必须先于活动vj进行。这种的有向图叫做用边表示活动的网络，简称AOE（activeonedges）网络。AOE网络在某些工程估算方面非常有用。他可以使人们了解：（1）：研究某个工程至少需要多少时间？（2）：那些活动是影响工程进度的关键？在AOE网络中，有些活动可以并行的进行。完成不同路径的活动所需的时间虽然不同，但只有各条路径上所有活动都完成了，这个工程才算完成。因此，完成整个工程所需的时间取决于从发点到收点的最长路径长度，即在这条路径上所有活动的持续时间之和。这条路径长度就叫做关键路径（criticalpath）

27、。1956年，美国杜邦公司提出关键路径法，并于1957年首先用于1000万美圆化工厂建设，工期比原计划缩短了4个月。杜邦公司在采用关键路径法的一年中，节省了100万美圆。案例自发点(记为v1)开始沿最长路径到达vi所需要的时间,称为vi的最早完成时间,记作TE(vi),i=1,2,n.vi(i1)的最早完成时间可按如下公式计算:收点vn的最早完成时间TE(vn)就是从v1到vn的最长路径的权.（2）最早完成时间在保证收点vn的最早完成时间不增加的条件下,自v1最迟到达vi的时间称为vi的最晚完成时间,记作TL(vi).TL(vn)=TE(vn).in时,vi的最晚完成时间由下面公式计算:（3）

28、最晚完成时间称TL(vi)-TE(vi)为vi的缓冲时间,记作ES(vi)=TL(vi)-TE(vi)i=1,2,n在关键路径上各顶点的缓冲时间均为0.（4）缓冲时间求所示PERT图中各顶点的最早、最晚和缓冲时间以及关键路径.31v5v3v4v234416v12v60v8v71442?例解(1)各顶点的最早完成时间:TE(v1)=0;TE(v2)=max0+1=1;TE(v3)=max0+2,1+0=2;TE(v4)=max0+3,2+2=4;TE(v5)=max1+3,4+4=8;TE(v6)=max2+4,8+1=9;TE(v7)=max1+4,2+4=6;TE(v8)=max9+1,6+

29、6=12.31v5v3v4v234416v12v60v8v71442(2)各顶点的最晚完成时间:TL(v8)=12;TL(v7)=min12-6=6;TL(v6)=min12-1=11;TL(v5)=min11-1=10;TL(v4)=min10-4=6;TL(v3)=min6-2,11-4,6-4=2;TL(v2)=min2-0,10-3,6-4=2;TL(v1)=min2-1,2-2,6-3=031v5v3v4v234416v12v60v8v714423)各顶点的缓冲时间:TS(v1)=TS(v3)=TS(v7)=TS(v8)=0;TS(v2)=2-1=1TS(v4)=6-4=2;TS(v

30、5)=10-8=2;TS(v6)=11-9=2.关键路径为v1v3v7v8.求关键路径的算法分析（1）求关键路径必须在拓扑排序的前提下进行，有环图不能求关键路径；（2）只有缩短关键活动的工期才有可能缩短工期；（3）若一个关键活动不在所有的关键路径上，减少它并不能减少工期；（4）只有在不改变关键路径的前提下，缩短关键活动才能缩短整个工期。CPM和PERT是两种分别独立发展起来的网络技术。其中关键路线法（CriticalPathMethod，简称CPM）是美国杜邦公司和兰德公司于1956-1957年联合研究提出的，CPM假设每项工序的作业时间是确定值，它考虑的是时间、资源，重点在于成本的控制；而计

31、划评审技术(ProgramEvaluationandReviewTechnigue,简称PERT)则是在1958年由美国海军特种计划局和洛克希德航空公司规划和研究在核潜艇上发射“北极星”导弹的计划,为协调3000多个承包商和研究机构而开发的，在PERT中工序的作业时间是用概率方法得出的估算值，有着不确定性，PERT主要是针对含有大量不确定因素的大规模开发研究项目的，它考虑的是资源、费用，重点在于时间的控制。艾兹格艾兹格迪科斯彻迪科斯彻EdsgerWybeDijkstra计算机先驱之一，他开发了程序设计的框架结构。与D.E.Knuth并称为我们这个时代最伟大的计算机科学家。艾兹格W迪科斯彻（Ed

32、sgerWybeDijkstra，1930年5月11日2002年8月6日）荷兰计算机科学家，毕业就职于荷兰Leiden大学，早年钻研物理及数学，而后转为计算学。曾在1972年获得过素有计算机科学界的诺贝尔奖之称的图灵奖。伟大的智者DonE.Knuth，中文名：高德纳(1938-)算法和程序设计技术的先驱者。个人主页：http:/www-cs-faculty.stanford.edu/knuth/一般说来，不知道此人的程序员是不可原谅的。其经典著作计算机程序设计艺术更是被誉为算法中“真正”的圣经。难怪连BillGates都说：“如果能做对书里所有的习题，就直接来微软上班吧！”对于DonE.Knuth本人，一生中获得的奖项和荣誉不计其数，包括图灵奖，美国国家科学金奖，美国数学学会斯蒂尔奖及发明先进技术荣获的极受尊重的京都奖等，写过19部书和160余篇论文，每一篇著作都能用影响深远来形容。DonE.Knuth也被公认是美国最聪明的人之一。