下载

1下载券

加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 图论建模

图论建模.ppt

图论建模

baiyi1056
2011-09-13 0人阅读 举报 0 0 暂无简介

简介:本文档为《图论建模ppt》,可适用于高等教育领域

数学建模讲座吉林大学方沛辰离散问题专题长江三峡之一景图论建模图论建模例中国古题:五斤葫芦三斤瓢八斤油两下约。三个容器容量分别是斤其中斤的容器里装着斤油怎样利用容积将油平分?引入状态概念:(xyz)表示三个容器里分别装的油的数量,起始为()。约定出现过的状态不得再出现。(,,)实际上我们用的是穷举法这个问题只有这两个解。其中第一个步骤最少是最好的解。实际上我们用的是穷举法这个问题只有这两个解。其中第一个步骤最少是最好的解。解题过程中借用了图论的工具即用“点”表示状态“边”表示状态间的转移关系。点和边的附加信息称为赋权这样的图称为赋权图有点权图、边权图的概念。例证明:任何六个人中,必有三人互相认识或三人互相不认识。这里提到的认识是互相认识类似于双方握过手。证明“怎样或怎样”的命题方法是否定一个证明另一个成立。我们用点表示人个人分别用ABCDEF表示。两个人互相认识就在两点之间连一个实线边互相不认识就用虚线连。于是所有的两点之间都有连线不是实线就是虚线。图论中把任何两点间都有连线的图称为完全图。问题转化为在描述任意个人的关系的图里如果没有实线三角形就一定有虚线三角形。分析:不妨从A考虑。不妨设A至少认识三个人进一步设至少认识BCD于是AB、AC、AD都是实线从没有实线三角形可以得出BC、BD、CD都只能是虚线所以ΔBCD为虚线三角形。不妨从A考虑。不妨设A至少认识三个人进一步设至少认识BCD于是AB、AC、AD都是实线从没有实线三角形可以得出BC、BD、CD都只能是虚线所以ΔBCD为虚线三角形。在A没有至少认识三个人时即最多认识两个人此时A至少不认识三个人把刚才的证明里的实线换为虚线虚线换为实线即得证。这道题目里面点表示人边表示人与人之间的关系。类似的几个可以用图论解决的问题类似的几个可以用图论解决的问题一人带一只狼、一只羊、一棵白菜过河船上只能是人带一个物件并且人不在时狼要吃羊羊要吃白菜怎样才能安全过河?两人轮流从颗火柴中取每次只许取一颗或两颗不可多取也不可不取最后取完者获胜如何能胜?件产品中有一件不合格重量上有差异有一台无砝码天平几次能找出来并知轻重?甲乙进行网球比赛谁连续两次获胜或总计胜三局则最后胜利试分析各种取胜情况。图论基本概念图论基本概念图论是用点表示对象边表示对象间的关系的数学模型。V是全部点构成的集合点共有n个E是全部边构成的集合边共有m条。G=(V,E)表示无向图边没有方向。D=(V,A,f)表示有向图在有向图里边称为弧,弧的全体记为A。f是每条边的方向的集合。点与点的关系称为邻接或不邻接边与点的关系称为关联或不关联。一个边总是和两个点关联当两个点是同一个点时称为环。当两个点之间有多条边称为平行边或多重边没有环和平行边的图称为简单图最常用的就是它。与点v关联的边的个数称为点的度或次记为deg(v)。度数为奇数的称为奇点度数为偶数的称为偶点。正则图:每个点有相同的度。完全图:任何两点间都有一条边显然完全图中每个点的度数都是n。将点和边的一些附加信息标在图上称为赋权图。路径:点和边构成的序列。边的个数称为路径的长度。简单路径:边不重复点可以重复的路径又称链。基本路径:点也不许重复的路径。回路(圈):起点和终点是同一个点的路径。类似也有简单回路和基本回路的定义以及回路的长度的概念。有向图中从u到v有路径则称u可达v(可达必有基本路径)从u到v的最短路的长度称u到v的距离记为d(u,v),不可达时为无穷大或无定义。(这里不是赋权图的距离)无向图的可达性是对称的故常考虑连通性。当G中任何两点间至少有一条路径称G是连通的否则是非连通的。去掉一个点图就成为不联通的这点称为割点去掉一个边图就成为不联通的这边称为割边。G无割点的充要条件G是不可分图。图的基本数据结构图的基本数据结构用图和网络建立模型解决问题时常要把所有信息输入计算机。设计的算法与数据在计算机里存储的数据结构有很大关系所以我们先要研究图的数据结构。邻接矩阵表示法邻接矩阵C是一个n*n的矩阵我们以有向图为例来介绍它。也就是说i与j间有弧cij就为否则就为每行之和是出度每列之和是入度。优点:简单、直观缺点:浪费空间查找慢。可用边权代替如果多种权可用多个阵点权可用下加一行来表示之。关联矩阵表示法关联矩阵表示法关联矩阵B是n*m矩阵元素可以是三种。也就是每行对应图的一个节点每列对应图的一个弧。如果一个节点是一条弧的起点则关联阵元素取是终点则取不关联则取。对于简单图每列只有两个非零元(一个一个)每行的个数恰好是出度的个数恰好是入度。优点:简单、直观还有许多重要性质。缺点:浪费查找慢。弧的顺序(,),(,),(,),(,),(,),(,),(,),(,)就是关联阵的列的标号括号外为边权。弧的顺序(,),(,),(,),(,),(,),(,),(,),(,)就是关联阵的列的标号括号外为边权。对于图与网络中的边权可以在关联矩阵下面增加一行来存储多个权就增加多个行。弧表表示法将图以弧表的形式存储也就是每个弧对应一个列从上到下分别是起点、终点和权。各列间从前到后按照起点、终点的字典序排列。这种结构存储效率比较高。邻接表示法邻接表示法将图以邻接表的形式存储就是每个节点用一个单向链表列出从该节点出发的所有弧链表中每个单元对应于一条出弧三个位置分别是终点、权和结束标志遇到表示结束。整个邻接表是一个指针数组。前一个例子可以表示为:星形表示法星形表示法星形表示法与邻接表示法的思想有一定的相似之处对每个节点它也是记录从该点出发的所有弧但不是采用单向链表而是采用一个单一的数组表示。也就是说该数组中首先存放从节点出发的所有弧接着存放从节点出发的所有弧依此类推。最后存放从节点n出发的所有弧。对每条弧要依次存放起点、终点、权等有关信息。为了快速检索引入一个数组记录每个节点出发的弧的起始地址(即弧的编号)因此又称为前向星形法。以前面的例子来看前星形法就是两个表格。前向星形表示法有利于查阅每个节点的出弧但不能快速检索每个节点的所有入弧为了快速检索入弧可以采用反向星形表示法。首先存入节点的所有弧然后存入节点的所有弧依此类推。同样给出一个数组记录每个节点的入弧地址。前向星形表示法有利于查阅每个节点的出弧但不能快速检索每个节点的所有入弧为了快速检索入弧可以采用反向星形表示法。首先存入节点的所有弧然后存入节点的所有弧依此类推。同样给出一个数组记录每个节点的入弧地址。如果希望两种都能快速检索可以综合采用前向和反向星形表示法。此时引入一个数组记录一条弧在两种表示法中的对应关系。给出前向表示法的基础上再给出换算关系。应用图的数据结构建模举例应用图的数据结构建模举例消防设施的布置。如图是一个点边的图表示某小区街道。上级要求每条街道都要安装一个消防栓请制定一个安装方案使安装的个数最少。显然只在交叉路口设立即可减少安装数量。采用关联矩阵的数据结构即C=(cij)*消防栓的设置问题可视为图的最小覆盖问题。寻找最小覆盖的算法(结果不唯一):寻找最小覆盖的算法(结果不唯一):在次数最大的顶点中任选一点vi划去关联矩阵vi的行中所对应的列及该行K=K{vi}重新计算各顶点的次数若还有列返回否则结束K即为所求。监狱看守的设置监狱看守的设置仍为上图表示某监狱内的通道设置点为牢房边为通道。看守在某牢房门口可通过通道看到其他牢房最少设几名看守?采用邻接矩阵处理这个问题。无向图时它是对称阵。算法:对AE采用求最小覆盖的算法。C={v,v}化学品的存放化学品的存放某化学品仓库许多制品间不宜放在一起需分放两个房间共需多少个房间才能安全存放?设共有种化学品a,b,c,d,e,f,g,其中不能放在一起的是(a,b),(a,d),(b,c),(b,e),(b,g),(c,d),(c,e),(c,f),(d,e),(d,g),(e,f),(f,g)共种要求。用图将不能放在一起的关系画出点表示制品边表示不能放在一起的关系设想每个房间标不同的颜色最少需要几个房间即最少需用几种颜色。相邻顶点标不同颜色顶点着色问题。我们希望用一种颜色染更多的点这样才能少用颜色就是将V进行划分划分为不含相邻顶点的若干子集。我们试探看本题可见含a的极大独立集为{a,c,g),(a,e,g)。我们试探看本题可见含a的极大独立集为{a,c,g),(a,e,g)。与极大独立集互补的是极小覆盖:如果从覆盖K中去掉任何顶点都会使K不是覆盖则K为极小覆盖。问题转化为求出全部的极小覆盖。极小覆盖的性质:当且仅当对每个顶点要么v∈K要么v的所有邻点∈K并且二者不能同时成立时K为极小覆盖。我们利用这个性质构造求极小覆盖的逻辑算法:对任意v∈V要么选择v要么选择v的所有邻点。逻辑代数中“和”运算和“积”·运算分别对应着集合论的“或”∪和“交”∩运算。选择a或选择a的所有邻点b,d应表示为abd。就这样求全部极小覆盖归结为:得到全部极小覆盖为{a,c,e,g},{b,c,d,e,g},{b,d,e,f},{b,c,d,f}他们的补集为{b,d,f},{a,f},{a,c,g},{a,e,g}得到全部极小覆盖为{a,c,e,g},{b,c,d,e,g},{b,d,e,f},{b,c,d,f}他们的补集为{b,d,f},{a,f},{a,c,g},{a,e,g}包含顶点数目最多的独立集称最大独立集其中的顶点数目称独立数。任取上述三个之一的S={b,d,f}染第一种颜色再对G中去掉S求全部极大独立集得到{a,c,g},{a,e,g},取S={a,c,g},染第二种颜色G中去掉S、S只剩顶点e于是S={e}。问题彻底解决不可能用两种颜色完成。顶点着色、边着色、面着色是不同的问题但是可以互相转化方法就是利用图的定义:点表示对象边表示对象间的关系。面着色点着色例从一笔画谈起从一笔画谈起我们通常说起的一笔画可以有两种含义就是笔放下去后连续画出简单路径或者基本路径。一个图本身就是简单路径称这个图为欧拉图一个图本身就是基本路径称这个图为哈密顿图。前面学过:简单路径:边不重复点可以重复的路径又称链。基本路径:点也不许重复的路径。例:左边这个图是一个点边的图能否用三笔(简单路径)将其画出?不能。这个图的个点都是奇点而奇点只能作为起点或者终点至少要笔。例:是否是欧拉图?是!图中恰好有两个奇点一个为起点另一个为终点是否有哈密顿路?有!例如欧拉图和哈密顿图的概念没有太大的应用至多用于公园、博物馆、影展等的路线设计。影展常将整个展厅布置成单边有内容的走廊我们视为“边”而走廊和走廊的交点视为“点”。游览路线应该是欧拉路线。到动物园里看到所有的动物是每个游客的愿望他不必把所有的路线都走遍于是追求哈密顿路线。下面我们把两个概念推广得到和应用联系密切的模型。旅行商问题TravelingSalesmanProblem简称TSP一名推销员准备前往若干城市推销产品如何设计一条最短的旅行路线?(从驻地出发经过每个城市至少一次最后返回驻地)将这些城市之间的所有路线画在一个图上路程作为边权。选择一个回路使得回路经过所有城市且最短。这里不是求简单回路和基本回路但是可认为是哈密顿问题的推广应用面很广。中国邮递员问题ChinesePostmanProblem简称CPP一名邮递员负责投递某个街区的邮件如何设计一条最短的投递路线?(从邮局出发经过投递区内每条街道至少一次最后返回邮局)可以认为这是欧拉问题的推广也有广泛的应用。这些都是组合优化里重要的问题它们还可以再推广。例:B题灾情巡视路线下图为某县的乡(镇)、村公路网示意图公路边的数字为该路段的公里数。今年夏天该县遭受水灾。为考察灾情、组织自救县领导决定带领有关部门负责人到全县各乡(镇)、村巡视。巡视路线指从县政府所在地出发走遍各乡(镇)、村又回到县政府所在地的路线。若分三组(路)巡视试设计总路程最短且各组尽可能均衡的巡视路线。假定巡视人员在各乡(镇)停留时间T=小时在各村停留时间t=小时汽车行驶速度V=公里小时。要在小时内完成巡视至少应分几组给出这种分组下你认为最佳的巡视路线。在上述关于T,t和V的假定下如果巡视人员足够多完成巡视的最短时间是多少给出在这种最短时间完成巡视的要求下你认为最佳的巡视路线。若巡视组数已定(如三组)要求尽快完成巡视讨论Tt和V改变对最佳巡视路线的影响。分析这个题目先看第一问本质是求什么?若分三组(路)巡视试设计总路程最短且各组尽可能均衡的巡视路线。这是一个优化问题全部人员分三组各村镇都至少有一组去一次是约束总路程最短和各组尽可能均衡是目标。如何对v进行划分然后对三个子图求三个旅行商问题就是这个问题的实质了。我们可以简化称其为“多旅行商”问题。多旅行商问题是没有好算法的但就这样一个具体的问题还是能够找出它的结果的。此问题已经不是一个简单的图论问题这个问题已经进入一个新领域组合数学。组合数学:如何按照一定的规则安排一些离散个体的有关问题。包含哪些内容:存在性问题构造或枚举问题组合计数组合优化。用vi表示第i组所去的点且从这个问题可以看出实际问题常常很复杂需要简化为多个简单问题。例:幻方将…n排列成n*n方阵使每行、每列、每条对角线上的n个数字之和都相等。例如阶幻方:显然所有数字之和为n(n)每行的和应为n(n)对每个正整数n存不存在n阶幻方?有几个?怎样找?例:名选手参加的羽毛球单淘汰赛到结束共需多少场比赛?算法:=算法:每场比赛淘汰人共淘汰人需场比赛。例:一个边长为的立方体要切割成个边长为的小立方体切割时可以重新排列被切割的位置共需多少次切割?如果将各种组合情况都列举出来再找出切割次数最少的将很麻烦。显然六刀可以切出在原立方体中心的小块的每个面都是新切割出的面共有六个面说明至少要六刀。组合问题里总是利用各种技巧!我们常把组合论分为组合理论与组合优化鸽巢原理:把n个物体放到n个盒子里则至少有一个盒子里含有两个或两个以上物体。(加强形式):设q,q,…,qn都是正整数若qq…qnn个物体放入n个盒子里则第一个盒子里至少含有q个物体或者第二个盒子里至少含有q个物体…或者第n个盒子里至少含有qn个物体。Ramsey定理和Ramsey数的一般叙述比较难我们看简单情况。设G是点完全图K如果对每条边任意涂以红色或者蓝色则G中一定包含一个红色三角形或者包含一个蓝色三角形。这就是我们前面讲到的互相认识问题显然对于kn在n>=时都是成立的。就是这种情况下的Ramsey数即N(,)=。设G是点完全图K如果对每条边任意涂以红色或者蓝色则G中一定包含一个红色三角形或者包含一个蓝色完全四边形。即N(,)<=通过别的方法可知N(,)==N(,)进而N(,)=。和数学建模联系密切的是组合优化。在组合优化的学习中首先应该知道一些常见的模型将来把需要解决的问题往已有模型上联系或者套用现有模型或者有针对性地设计算法寻求解决。引用一个工具:整数规划IP采用一种方法模型转化。假设大家对线性规划LP、整数规划、规划都比较熟悉。背包问题有一个徒步旅行者只带一个包许多物品都有带的价值每个物品有自己的重量和价值怎样装背包使得不超过背包的重量限制而总价值最大?记共有n件物品第i件重wi价值vi背包容量为Bx…xn为变量则装箱问题需要n个木料长度分别为a…an都要从长度为B的原料上截取怎样安排用原料根数最少?等价问题n个物品重量分别是a…an有一种承重为B的箱子怎样装箱用箱子数最小?有些组合优化问题用IP表示很繁琐也很难理解还是用语言叙述。图论也属于组合轮的范畴所以图论优化问题也是组合优化问题。最短路问题在有多种行车路线的情况下司机要从甲地驾车到乙地选哪条路线更近?(SPPshortestpathproblem)有Dijkstra算法Floyd算法动态规划等多种算法。公路连接问题某地区有若干个城市现要修建高速公路把这些城市连接起来使得其中任何一个城市都可经高速公路直接或间接的到达另一个城市。假定已知任意两个城市之间修建的成本怎样修成本最小?修建的高速路每个结点都是“N”型时这是一个求基本路径问题修建的高速路有结点都是“Y”型时这是求最小生成树问题。运输问题将m个产地生产的原料运往n个使用这些原料的工厂假设所有的产量和用量都已知如何调配运输使总运量最小?一般来说用线性规划或整数规划即可求解。CPP问题TSP问题指派问题要安排n个人去完成n项任务每人一项不同的人完成不同的任务获得的回报不同怎样安排回报最大?TSP问题的整数规划形式:记从i到j的距离为dij(此时有对称和不对称的区别)对一般的TSP可写为:Xij取表示选择走从i到j的路取表示不走。目标函数的含义是选中的路的总长最小前两组约束的含义是每个城市有唯一的前方城市和后方城市。最后一组约束是为了避免循环。指派问题很容易写成规划的形式目标函数是总回报约束两组:每人完成一项工作每项工作一人做。还可以有各种变形这个模型的应用很广。有约束机器排序问题n个加工量为{di|i=…n}的产品要在一台机器上加工机器在第t时段的工作能力为ct求完成所有产品加工的最少时段数。它的数学模型可写为:其中xitT为决策变量xit=表示第i时段加工产品i目标是所需时段数最小约束是每个工件只在一个时段加工与加工能力约束。算法复杂性与启发式算法所有组合最优化问题其组合方式的数量一定是有限的所以可以逐个列举出来再选择最优即都可用穷举法找出最优解。对组合优化问题我们关心的一般不是最优解的存在性和唯一性而是如何找到一个有效算法求得一个最优解。可是随着问题规模的扩大穷举付出的时间代价却越来越大。例:非对称的TSP问题它的可行解可以用n个城市的一个排列表示当起(终)点为固定时可行解的个数显然是(n)!用穷举法找最优解就要枚举(n)!次。设秒钟可以计算出个城市的TSP个城市则要用秒个城市要用*秒=分…。到只相差个城市计算时间相差百年也就是用穷举法已经不能解决了此时称这个算法是无效的。给出两个概念:问题、实例问题是一个抽象的模型或概念通过具体的数据表现出来我们前面介绍的就是九个问题。一种类型所有的具体实例的全体。具体的问题叫实例问题是通过所有的实例来实现的。算法是针对问题设计的使用时却要面对不同的实例。衡量算法的好坏通常用一个实例在算法执行时的加减乘除及比较等基本运算的总次数同实例在计算机计算时的二进制输入数据的大小关系来度量。简单说就是计算总次数和输入长度之间的关系来确定。对于一个正整数x二进制表示是以x=assass…aa的系数(asas…aa)来表示其中as=ai=,i=,,…,s。X的二进制位数s称为x的输入长度在logx与logx之间不超过注意和的输入长度都是所以规定Log=后上面的二进制表示法和输入长度的结论可以推广到非负整数。常规理解计算机只能用有限位表示一个实数因此我们限定只考虑有理数。下面用TSP问题的枚举算法为例介绍计算复杂度的计算。输入数据是城市数n和所有城市间的距离{dij|<i,j<n,i<>j},假设这些数都是整数。对任何一个非零dij的二进制输入长度不超过二进制输入总长度不超过L=n(n)log|P|,其中,设dij有上界k则L<=n(n)(logk)输入长度是城市数n的二次函数。城市数为n设第一个城市为始终点。求路径(,i,…,in,)的长度的基本运算为n个两两城市间距离的和共有(n)!条路径枚举所有路径进行(n)!次比较可得最优路径。这个算法的总计算次数可估算为{(n)!}n=n!最后TSP枚举算法的输入是n的多项式函数总计算是阶乘函数。我们对实例的二进制输入长度和算法的基本计算总次数一般是进行粗略估计通常只给出一个上限。一个求解实例I的算法的基本计算总次数C(I)同实例I的二进制输入长度d(I)的关系常用C(I)=f(d(I))=O(g(d(I)))来表示含义是计算总次数C(I)是输入长度D(I)的一个函数这个函数被另一个函数g(x)控制即存在一个函数g(x)和一个非负常数α使得此式中g(x)的函数特性决定了基本计算总次数的特性。当存在一个多项式函数g(x)使上式对任意实例都成立时称算法为多项式时间算法简称多项式算法又称好算法若不存在一个多项式函数g(x)使上式成立时称算法为非多项式时间算法或指数时间算法简称指数算法又称不好算法。(进一步细分还可定义强多项式算法、伪多项式算法等。)这样我们把所有的算法进行了分类。例:解决最短路问题的Dijkstra算法和Floyd算法是多项式算法穷举法(枚举法)是不好算法隐枚举法也是不好算法单纯形法是指数算法但遇到不好算例的概率为零动态规划算法是指数算法。一个算法是针对一类问题的所有算例而编制的。我们再来对问题进行分类。给定的一个优化问题若存在一个多项式算法则称这个问题是多项式问题所有的多项式问题的全体称为P。最短路问题是P问题。尽管单纯形法不是P算法不能就此确定线性规划问题的归属年苏联Khachian构造了解决线性规划的椭球算法并证明是多项式时间算法此后又有一些学者提出许多种内点算法也是多项式算法从而确定线性规划问题属于P。装箱问题、TSP问题、机器排序问题、整数规划问题等多数组合优化问题都不属于P。按照定义至今还没找到多项式算法的问题称为非多项式问题简称NP问题。显然NP问题非常多需要再分类。一种分法就是把等价的问题化为一类。等价就是可以用模型转化的方法互相变来变去的重要的一个模型就是整数规划模型。大家公认简单直观的难题是旅行商问题前面看到它等价于整数规划模型穷举的计算量是阶乘级的显然是指数算法。既然等价计算的难度就与整数规划问题一致。把与它们都一致的化为一类名字叫做NPComplete中文NP完全问题简称为NPC。含义是其中有一个如果将来能找到多项式算法那么所有的都是P问题这是不可能的说明任何一个永远也不会找到多项式算法所以这是最难的问题的集合。这样的问题随着规模的扩大解决起来的实际计算量指数式的膨胀求最优解的通用算法是无法实现的。所以又称为NPhard,NP难的。对于大型的NPC问题必须变换思路找出新的解决方法。

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

文档小程序码

使用微信“扫一扫”扫码寻找文档

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/41

图论建模

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利