资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。感谢您,数学试验,第十二章,图基本概念与算法初步,云南大学信息学院通信工程系,宗容,第1页,第十二章 图基本概念与算法初步,12.1 问题提出,12.2,图概念和术语,12.3,图矩阵表述方法,12.4 常见应用网络图模型,12.5 算法,试验题,第2页,12.1,问题提出,图研究对象网络，网络优化,可见网河道网、浇灌网、公路网、铁路网、电话线网、计算机通讯网、输电线网,不可见网各种关系网，如各种状态转移关系、事物相互冲突关系、工序时间先后次序,基本网络优化问题：,最短路径、最小生成树、最大流、最小费用流,处理方法：线性规划、网络分析,本试验目标,：,掌握怎样建立图模型,了解图存放结构，学会图表示与矩阵表示之间转化,对算法及其复杂性建立初步认识，并树立算法有效性观点,第3页,12.1.1,七桥问题,18世纪东普鲁士哥尼斯堡被普利格尔河分为四块，经过七座桥连接。,问题：一个散步者怎样才能从某块陆地出发，经每座桥一次且仅一次回到出发点,结果：没有些人能够做到,第4页,七桥问题,1736年，著名数学家欧拉(Euler)证实了他猜测。,方法：,将南北两岸和两个岛A,B,C,D抽象成四个点，将连接这些陆地桥用线段表示,结果：,将问题转化为是否存在从某点(顶点)出发经过每条线(边)一次且仅一次最终回到出发点路线,第5页,七桥问题,该问题是欧几里德几何学没有研究过问题。这里引出图形、线段长短、曲直、顶点准确位置都无关紧要，主要是点线之间连接关系。,欧拉指出：一个线图中存在经过每边一次且仅一次回到出发点路线,充要条件,是：,1）图要是连通；,2）与图中每一顶点相连边必须是,偶数条,结论：七桥问题无解,第6页,12.1.2,古典过河问题,问题：,设有n个正常人和n个精神病患者要过一条河。现只有一条能容纳C（C2n）人小船，为预防患者伤害正常人，要求不论在河岸哪一边正常人个数不得少于患者个数（除非正常人个数为0）。又设每个人都会划船，试,设计一个过河最正确方案,（小船往返次数最少）。,问题复杂，先结构出对应数学模型。,解：,用三元组(x,y,t)表示渡河过程中某个状态,x起始岸上正常人个数,y起始岸上患者个数,t小船位置,第7页,古典过河问题,结构一个图,图中每一个,顶点,代表一个,正当状态,，不难得出正当状态下，(x,y,t)必须满足：x=0，or x=n，or x=y,图中,边,则表示该边,所依附两个顶点,（即两个正当状态）,间,可由一次划船而,相互转换,例，当n=2,C2时，各正当状态及其转换如图所表示,(0,2,0)(0,2,1),(2,2,1)(2,0,0)(2,1,1)(0,1,0)(0,0,0),(1,1,0)(1,1,1),(2,1,0),第8页,古典过河问题,可见，通路最正确方案不唯一,上面过河方案求解就转换成一个图搜索问题，及搜索一个图，找出从起始顶点(n,n,1)到目标顶点(0,0,0)一条包含边数最少通路，若无，则给出无解信息。,与上述两个问题相关更实际问题是“中国邮路问题”，它是由中国数学家管梅谷教授首先提出而得名。设邮递员从邮局出发，遍历它所管辖每一条街，将信件送出后返回邮局所走路径最短。若他所管辖街道组成回路，则这条回路便是所求路径。如若不是，则必定有些街道需走多于一遍，这时需寻求,最短路径,。,又如1998年全国大学生数学模型竞赛B题“最正确灾情巡视路线问题”，也属于,最短路径,问题，即最正确推销员回路问题。,第9页,12.2,图概念和术语,1、图：,图G由集合V(G)和E(G)组成，记为G=(V,E),V,(G),顶点,(图中结点)非空有穷集合,E,(G),边,有穷集合(相关顶点偶对称为边),通惯用V，E分别表图顶点集、边集，图G可用(V，E)表示。,V=a,b,c,d，,E=(a,b)，(a,c)，(a,d)，(b,c)，(b,c)，(b,d)，(b,d)。,第10页,图概念和术语,2.有向图,(directed graph),：,图中边是顶点有序对,有向边，又称为弧，用尖括号表示,从v,i,到v,j,一条弧,V,i,边始点(尾顶点),V,j,边终点(头顶点),3.无向图,(undirected graph),：,图中边是顶点无序对,无向边，用圆括号表示,（v,i,v,j,）顶点v,i,与v,j,相连一条边,图中顶点a,b,c,d和边端点对为：,e,1,=(a,b)，e,2,=(a,c)，e,3,=(a,d)，e,4,=(b,c)，e,5,=(b,c)，e,6,=(b,d)，e,7,=(b,d),v,i,v,j,v,i,v,j,第11页,图概念和术语,4.子图,：图G=(V,E)，G=(V,E)，,若V(G)V(G)，且E(G),E(G)，则称G是G子图,简单图：,无重边，无环图,完全图：,任意两顶点都有边相连图,第12页,顶点与边术语,5.顶点度TD(v,i,)：,与该顶点相关联边数目,对有向图，把以顶点v为尾弧数目称为顶点v,出度,，即OD(v,i,)（或d,+,(v,i,)）,把以顶点v为头弧数目称为顶点v,入度,，即ID(v,i,)（或d,-,(v,i,)）,顶点度,：TD(v,i,)=ID(v,i,)+OD(v,i,),若图G有n个顶点，e条边或弧，则,第13页,图概念和术语,顶点与边几个术语：,1)若边e端点为u，v，则称,e与顶点,u,v相,关联,2)若顶点u,v之间有边相连，则称,u与v相邻,3)若边,e1，e2,与同一顶点相关联，则称,相邻,4)端点相同两边称为,重边,两端点为同一个点一条边称为,环,现有有向边又有没有向边图称为,混合图,第14页,路和连通性,6.路径,：从V,p,经过V,i1,V,i2,V,in,到V,q,，则称该顶点序列为从顶点V,p,到顶点V,q,一条路径,路径长度,：定义为路径上边数目,简单路径,：假如一条路径上顶点除V,p,和V,q,能够相同外，其它顶点都不一样，则称此为一简单路径,回路(或环),：V,p,=V,q,简单路径,第15页,路和连通性,7.连通图,：无向图G中，从v,i,到v,j,有一条路径，则称v,i,到v,j,是连通,若图G中任意两个顶点v,i,和v,j,(v,i,v,j,)都是连通，则称此无向图G为连通图,一个无向图,连通分量,定义为此图极大连通子图,强连通图,：在有向图G中，任意两个顶点v,i,和v,j,(v,i,v,j,)都连通，即从v,i,到v,j,和从v,j,到v,i,都存在路径，则称该图G为强连通图。,有向图G中极大强连通子图称为G,强连通分量,第16页,图概念和术语,8.网络或带权图,：图中每一条边附加一个数作为权图（赋权图）,若给每条边赋予一个或多个实数,第17页,12.3 图矩阵表示方法,邻接矩阵,关联矩阵,边矩阵、边权矩阵,第18页,1、邻接矩阵,无向图邻接矩阵：A=(a,ij,),nn,，其中,第19页,有向图邻接矩阵,有向图，其邻接矩阵A=(a,ij,),nn,中元素a,ij,取为,v,i,指向v,j,有向边数目，,图中有向图邻接矩阵为,1 2 3 4 5,1 2,3 4 5,第20页,网络图带权邻接矩阵,A=(a,ij,),nn,，其中a,ij,取为v,i,指向v,j,有向边上权。当无边时取为，对角线上元素为0。,第21页,2、关联矩阵,无向图关联矩阵：M(m,ij,),nm,，其中,第22页,3、边矩阵、边权矩阵,边矩阵：,定义一个2m矩阵E，第一、二行分别存放边起点和终点。若第i条边e,i,起点和终点分别为v,j,，v,k,，则E(1，i)=j，E(2，i)k,对加权图，只需增加一行来存放各条边上权，这么矩阵称为,边权矩阵。,第23页,12.4 常见应用网络图模型,1、田径赛时间安排问题,2、人狼羊渡河问题,3、最正确灾情巡视路线问题,4、运输问题,第24页,1.田径赛时间安排问题,问题：,设某校田径赛共设六个项目标比赛：跳高、跳远、标枪、铅球、100m、200m，要求每个选手至多参加三个项目标比赛，现有五名选手报名参赛，选手所选项目以下表所表示，要求,设计一个竞赛日程安排表,，使在尽可能短时间内安排完比赛。,姓名,丁一,马二,张三,李四,王五,项目1,跳高,标枪,标枪,铅球,跳远,项目2,跳远,铅球,100m,200m,200m,项目3,100m,200m,跳高,第25页,2.田径赛时间安排问题,设计一个图，图中,顶点,代表,竞赛项目,，在全部两个,不能同时进行,比赛,项目,之间连上一条,边,。,显然，同一选手选择几个项目不能同时比赛，所以该选手所选择项目中应该两两有边相连，可得如图所表示模型。,A,B,D,F,C,E,100m,200m,标枪,铅球,跳远,跳高,姓名,丁一,马二,张三,李四,王五,项目1,跳高,标枪,标枪,铅球,跳远,项目2,跳远,铅球,100m,200m,200m,项目3,100m,200m,跳高,第26页,田径赛时间安排问题,竞赛项目标时间安排问题能够抽象为对该无向图进行,“着色”,操作，即使用尽可能少颜色去给图中每个顶点着色，使得,任意两个有边相连接相邻顶点着上不一样色,。,A,B,D,F,C,E,100m,200m,标枪,铅球,跳远,跳高,每个颜色表示一个比赛时间，着同一色顶点能够安排在同一时间内竞赛。,只要,安排4个不一样时间段,竞赛即可。,第27页,第28页,第29页,第30页,第31页,第32页,第33页,第34页,3、最正确灾情巡视路线问题,这是1998年全国大学生数学模型竞赛B题中两个问题.,今年夏天某县遭受水灾.为考查灾情、组织自救，县领导决定，率领相关部门责任人到全县各乡（镇）、村巡视.巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地路线.,(1)若分三组（路）巡视，试设计总旅程最短且各组尽可能均衡路线.,(2)假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时.要在24小时内完成巡视，最少应分几组；给出这种分组下最正确巡视路线。,第35页,图12.10 乡镇、村公路网示意图,第36页,问题分析：将公路网图中，每个乡（镇）或村看作图中一个节点，各乡（镇）、村之间公路看作图中对应节点间边，各条公路长度（或行驶时间）看作对应边上权，所给公路网就转化为加权网络图.,问题转化为在给定加权网络图中寻找从给定点O出发，行遍全部顶点最少一次再回到O点，使得总权（旅程或时间）最小，此即最正确推销员回路问题。,在加权图G中求最正确推销员回路问题是NP完全问题，即这类问题中迄今为止没有找到一个有效算法，它大型实例不能用准确算法求解，必须寻求这类问题有效近似算法。,第37页,4、运输问题,在战争时期，要把后方基地S物质，经过铁路运到前方t处，能够认为在某条铁路上可运输物资总量是有限，若把某条线路上最大运输量称为它容量，请你给出一运输方案，在确保每条运输线上不超出容量前提下，使得后方运到前方物资总运量最大.,图12.11 连接前后方铁路网,v,1,v,2,v,3,v,4,v,s,v,t,5,9,4,6,8,3,4,8,7,4,第38页,问题分析：,所谓运输方案，即从基地运出多少物资，其中多少吨可沿某条路送到前线，使得总容量最大，送最多。而每条运输线上运输量必须满足以下条件：,实际运输量不能是负；,每条弧实际运输量不能大于该弧容量；,除了起点和终点外，对其它顶点来说，全部指向该节点弧上运输量应等于全部从该点运出运输量和。,第39页,假如用某运输方案将500吨物资从基地运到前方，这个铁路网上运输量是否还能够提升，或者说该网络最大输送量是多大？就是我们要处理最大流问题。,从以上几个问题中能够看出，利用图论方法建立模型关键是怎样将要讨论问题转化为图论问题，那些实际问题能够用图中顶点和边来代表，如田径赛中时间安排问题，用顶点代表竞赛项目，在全部两个不能同时进行比赛项目之间连上一条边，这么所讨论问题转化为图论问题，问题求解也就变成了网络图论中问题。,第40页,12.5 算法,算法,算法定义,算法特征,算法评价,算法分析,评价算法效率惯用方法,算法时间复杂性分析,时间复杂度,量级比较,算法空间复杂性分析,第41页,1、算法,当代社会，许多问题处理都离不开计算机程序,我们不但需要算法，而且更需要好算法。但有些算法可能花费很长时间,比如：用行列式定义来求一个20阶行列式值，即使是每秒l000万次计算机也要花大约15万年时间。,从定义出发求n阶行列式值算法不可取，它即使正确，不过无效。,故寻找一个问题有效算法非常主要。,怎样才能简便地判断一个算法有效性呢?,在什么情况下一个问题找不到有效算法来求出正确解？,第42页,(1)算法定义,算法是处理某一特定类型问题有详细步骤方法。,表述一个算法普通有两种方法：,步骤描述 框图,第43页,(2)算法特征,一个算法应该包含5个特征,有穷性：,一个算法必须在执行有限步之后结束,确定性：,算法每一步必须是确切地定义，无二义性。对于每种情况，有待执行运算必须被严格和清楚地要求,可行性：,算法应该是可行，即算法中描述运算都是相当基本，他们都是能够经过已经实现基本运算执行有限次来实现,输入：,一个算法有0个或多个输入。他们在算法开始之前对算法给定量。这些输入取自于特定集合,输出：,一个算法有1个或多个输出。它们是同输入有某种特定关系量。,第44页,(3)算法评价,求解一个问题能够有各种算法，判断一个算法好坏主要有以下标准：,正确性,能满足详细问题需求，反应求解问题对输入、输出和加工处理等需求,可读性,便于阅读，利于了解和求解,健壮性,含有差错和处理功效,效率,算法运行对资源占用多少-时间、空间,第45页,2、算法分析,在算法是“正确”前提下，对算法在计算机上执行耗时和所占空间分析，经常是人们对算法进行评定和选择主要依据。,确定算法效率一个惯用方法为：,运行测定法事后统计法,把算法用某种高级程序语言编写成程序,在特定计算机上输入选定数据运行,测量实际运行时间,事前分析估算法算法依赖于问题规模,但它反应计算机系统综合效率，并非单纯算法效率,(1)确定算法效率惯用方法,第46页,（2）算法时间复杂性分析,1)时间复杂度,用一个整数表示一个问题输入数据量大小(或输入长)，称为问题规模。,比如，行列式大小可用其阶数n来度量，所以n就是“求n阶行列式值”这个问题规模；图问题规模就是其边数或顶点数。,一个算法时间复杂度能够简单地定义为：从输入数据到计算出结果所需时间，它是问题规模(或输入长)n函数，记为T(n)。,第47页,时间复杂度T(n),同一算法计算机执行时间与计算机型号、程序语言及程序员技能等等相关,所以，这个时间无法准确度量，我们需要基于算法本身来确定算法时间复杂度T(n)，而不受机型以及这个算法怎样编码等等原因影响.,第48页,度量T(n)一个较恰当方法是，计算这个算法所需基本操作，这些基本操作包含加、减、比较、乘、除、交换存放位置，更粗略、更宏观地，我们计算这个算法必须执行步骤数目，它是实例输入长函数，,第49页,n-问题规模(输入长)，第一句计算时间为一个常数c,1,，后面比较、赋值语句要重复n次，所花时间不超出n常数倍，即c,2,n。总计算时间不超出c,1,c,2,n，这是一个与n同阶量，即有c,1,+c,2,nO(n)，这里,“O”表示数量级,，读作“n阶”，我们称O(n)为这个算法时间复杂度。,比如，求n个数最大者一个算法以下,max-999999,for i=1：n,if number(i)maxn,maxnmumber(i),end,end,记T(n)为这个算法时间复杂度。,通常记为:,T(n)=O(n),第50页,若存在正数C和n,0,，使当nn,0,时，一个算法执行时间T(n)Cf(n)，则称该算法花了f(n)阶时间，记为T(n)O(f(n)。,例：对下面三个简单程序段，求时间复杂度,1）,x=x+1,2）,for i=1:n,x=x+1,3）,for i=1:n,for j=1:n,x=x+1,end,end,时间复杂度分别是O(1)，O(n)，O(n,2,),第51页,比如求两个n阶方阵乘积C语言算法以下：,#define N 100,void matrixmultiply(int a NN,int b NN,int c NN),int i,j,k;,for(i=0;i N;i+)/*语句(1)*/,for(j=0;j N;j+)/*语句(2)*/,c ij=0 /*语句(3)*/,for(k=0,k N;k+)/*语句(4)*/,c ij=c ij+a ik*b kj /*语句(5)*/,语句(1)到语句(5)执行次数分别为：n+1、n(n+1)、n,2,、n,2,(n+1)、n,3,，它们之和即为算法时间花费：,T(n)=2 n,3,+3n,2,+2n+1。,当问题规模趋向无穷大时，有,第52页,第53页,第54页,第55页,2、计算复杂性函数量级比较,定义:设有两函数f,1,(n)与f,2,(n)，令,1)若0L，称f,1,(n)与f,2,(n),同量级,，记为O(f,1,(n)O(f,2,(n)；,2)若L=0，则称f,1,(n)量级比f,2,(n),低,，记为O(f,1,(n)O(f,2,(n),显然有,O(1)O(Log n)O(n)O(nLog n)O(n,2,)O(n,3,)0(2,n,)O(n!),第56页,第57页,第58页,（3）空间复杂度,类似于算法时间复杂度，以空间复杂度作为算法所需存放空间花费度量,记为：S(n)=O(f(n),空间单位普通要求为一个简单变量（如整型、字符型等）所占存放空间大小。,其中,n问题规模,，,f(n),算法处理数据所需,存放空间,与算法操作所需,辅助空间之和,在分析空间开销时，除关心“静态”分配空间外，还尤其注意“动态”申请空间和递归调用带来空间开销,第59页,试验一 商人们怎样安全过河,有3个商人带着随从要过一条河。随从们密约，在河任一岸，一旦随从人数比商人多,就杀人越货。不过乘船渡河方案由商人决定，商人们怎样才能安全过河。假设每人均会划船，小船一次只能容纳2人，且船在起始岸边。请给出安全过河最正确方案。,第60页,试验二 工作分配问题,有A、B、C、D、E五个同学将被安排去负担a、b、c、d、e五项工作，他们能胜任工作见表12.2，问是否存在一个工作分配方案，使每位同学分别担任一项他能胜任工作。,a,b,c,d,e,A,B,C,D,E,表12.2 AE同学能胜任工作表,第61页,试验三 给出以下三个简单程序段时间复杂度,1）x=5;n=100;,for i=1:n,x=x+1;,End,2）i=1;,while(i n),i=i*2;,end,3）x=10;,for i=1:n,for j=1:m,x=x+1,end,end,第62页,试验四 寻找有向路径算法分析,假设我们想确定在一个有向图G中，给定一对顶点s和c，是否存在从顶点s到顶点t有向路径。解这个问题一个算法陈说以下：,第一步,：Nodes。,第二步,：对以顶点Node为起点有向边终点，标上记号“可达”，对Node标上“已扫描”。,第三步,：若顶点t已经有了标识“可达”，则有向路径存在，算法终止，不然，继续。,第四步,：在标识为“可达”，而且还没有扫描顶点中任选一点u，Nodeu，返回第二步如没有这么顶点，则有向路径不存在。,（I）若图存放结构采取关联矩阵，求其时间复杂度。,（2）若图存放结构采取邻接矩阵，求其时间复杂度。,（3）这两个由不一样数据结构产生不一样算法时间复杂度不一样，哪个算法好?,第63页,3、P，NPC与NPH问题浅说,存在许多还没找到有效算法问题。,如其中最著名要数图论中“旅行推销员问题”，简称“TSP”,即“已给一个n个点完全图，每条边都有一个长度，求总长度最短经过每个顶点恰好一次封闭回路”。,这些问题称为NP难题(NPHard或NPH),迄今为止，这类问题中没有一个找到有效算法,当前倾向于接收,NP完全问题,(NPcomplet或NPC),和NP难题不存在有效算法,这一猜测，认为这类问题大型实例,不能用准确算法求解,，必须寻求这类问题,有效近似算法,。,第64页,P，NPC与NPH问题浅说,判定问题：其答案不是“是”就是“否”问题如，一个图两顶点之间存在路径吗?,判定问题有三类：P，NP和NPC。,P类,：已经有多项式时间算法判定问题；,NP类,：已经有指数时间算法判定问题，包含P类；,NPC类,：是NP一个子集，且其中每一个问题均能由NP中任何问题在多项式时间内转化而成。,问题A能在多项式时间内转化为问题B，可了解为：问题A有一个算法以问题B算法为子程序，当把每次对B算法调用看作一个基本操作(只花常数时间)时，A这个算法是多项式时间。,第65页,P，NPC与NPH问题浅说,在NPC问题之外还有一些问题，其难度与NPC相当或难度超出NPC，这就是NPH问题。,NPH类,：若问题A不属于NP类，已知某一NPC问题可在多项式时间之内转化为问题A，则称A为NP难题。比如，“TSP”是NPH问题。,第66页,注意,1）上述这些还不是严格定义，要准确说明P，NP和NPC问题定义需借助确定型图灵机(deterministic turing machines)和非确定型图灵机概念。,在一些文件中也将“NP难题”与“NP完全问题”混用。,3）NPC类问题是NP类问题中最因难一类问题，若NPC类中一个问题有多项式时间算法，则NP类中全部问题皆有多项式时间算法。,4）迄今为止，已证实为NPC类问题愈千个。其中，比较著名有：哈密尔顿路径问题、图着色问题、独立集、顶点覆盖问题、团问题、三维匹配问题等。,第67页,第68页,第69页,第70页,第71页,第72页,本章结束，,再见！,第73页,3、建模示例 商人们怎样安全过河,问题(智力游戏),3名商人,3名随从,河,小船(至多2人),随从们密约,在河任一岸,一旦随从人数比商人多,就杀人越货.,不过乘船渡河方案由商人决定.,商人们怎样才能安全过河?,问题分析,多步决议过程,决议,每一步(此岸到彼岸或彼岸到此岸)船上人员,要求,在安全前提下(两岸随从数不比商人多),经有限步使全体人员过河,第74页,模型组成,x,k,第k次渡河前此岸商人数,y,k,第k次渡河前此岸随从数,x,k,y,k,=0,1,2,3;,k=1,2,s,k,=(x,k,y,k,)过程状态,S=(x,y),x=0,y=0,1,2,3;,x=3,y=0,1,2,3;x=y=1,2,S,允许状态集合,u,k,第k次渡船上商人数,v,k,第k次渡船上随从数,d,k,=(u,k,v,k,)决议,D=(u,v),u+v=,1,2,允许决议集合,u,k,v,k,=0,1,2;,k=1,2,s,k+1,=s,k,d,k,+(-1),k,状态转移律,求d,k,D(k=1,2,n),使,s,k,S按,转移律,由s,1,=(3,3)抵达s,n+1,=(0,0).,多步决议问题,第75页,模型求解,x,y,3,3,2,2,1,1,0,穷举法 编程上机,图解法,状态s=(x,y)16个格点,10个 点,允许决议D 移动1或2格;k奇,左下移;k偶,右上移.,s,1,s,n+1,d,1,d,11,给出安全渡河方案,评注和思索,规格化方法,易于推广,考虑4名商人各带一随从情况,d,1,d,11,允许状态S,S=(x,y),x=0,y=0,1,2,3;,x=3,y=0,1,2,3;x=y=1,2,D=(u,v),u+v=,1,2,第76页,
展开阅读全文
浙ICP备2021020529号-1 | 浙B2-20240490 
