图论模型的构建.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,图论模型的构建,江苏省苏州中学 章维铣,一绪言,图论是数学的一个有趣的分支。1736年数学家欧拉（,Euler,1707,1783）,发表了一篇论文，用图的方法解决了著名的七桥问题，是图论建模的经典例子。,图论建模是指对一些客观事物进行抽象、化简，并用图来描述事物特征及内在联系的过程，就是抓住问题的本质，把问题抽象为点、边、权的关系。建立图论模型的目的和建立其它的数学模型一样，都是为了简化问题，突出要点，以便更深入地研究问题的本质；它的求解目标可以是最优化问题，也可以是存在性或是构造性问题。许多看似无从入手的问题，通过图论建模，往往能转化为我们熟悉的经典问题。,二图论建模方法,要素的选取,在建立模型之前，我们首先要对研究对象进行全面的调查，将原型理想化、简单化；然后对原型进行初步的分析，分清其中的各个要素及求解目标，理出它们之间的联系；下一步就是用恰当的模型来描述这些要素及联系。,【例1】,渡河问题,一个人带了一只狼、一只羊和一筐白菜想要过河。河上有一只小船，每次除了人以外，只能带一样东西。另外，如果人不在时狼就会吃掉羊，羊就要吃白菜。问怎样安排渡河，才能做到既把所有东西都带过河，而且在河上往返次数最少？,问题的要素有三点,：（1）人及他所带的3样东西；（2）人不在时狼就会吃掉羊，羊就要吃白菜，即人在渡河时，一岸上不能同时留下狼和羊或羊和白菜；（3）人每次至多带一样东西渡河，并要保证岸上的安全。,问题的求解目标,：,求河上往返次数最少的渡河方案。,对于要素（1），用字母,m,代表人，,w,代表狼，,s,代表羊，,v,代表白菜。,要素（2）、（3）可抽象为开始时设人和其他三样东西在河的左岸，这种情况用集合,mwsv,表示。在过河过程中左岸出现的情况有以下16种：,wmsv,mws,mwv,msv,wsv,mw ms,mv,ws,wv,sv,m s v w ,剔除下述6种可能发生狼吃羊，羊吃白菜的情况：（注意照顾右岸的情况）,wsv,ws,sv,mw ,mv,m,将剩下的10种情况作为图,G,的顶点，图,G,的边是按下述规则来连接的：如果情况,A,经过一次渡河可以变成情况,B，,就在情况,A,与情况,B,之间连一条边。根据这一规则，构造的图,G,如下面所示：,问题的求解目标就归结为：在图,G,中找一条连接顶点,mwsv,与,，,并且包含边数最少的路径。把图的边长设为1，那么渡河问题归结为求顶点,mwsv,到顶点,的最短路径问题。,【例2】方形柱体堆砌,有4个正立方体，它们的6个侧面各着以绿、蓝、红、黄4种颜色之一，如图1-2所示。现在要把这4个正方体堆成一方形柱体，堆成的方形柱体每个侧面4种颜色都有。,求解任务：1、这4个正方体能否堆成符合要求的方形柱体？,2、若能，找出一种堆砌方法。,【,方形柱体堆砌问题分析,】,一个正方体有6个面，所以4个正方体可以堆砌出为数十分可观的不同状态。就是确定了4个正方体依，次序从上到下排列，只考虑两两接触面不同，也有64=1296种排列，这里还没有考虑4个侧面的不同组合。若考虑到后者，又会衍生出许多各异的形式，先令第个正方体保持不动，正方体个有4个侧面，故有43=64种状态。因此即使在从上到下按序排列情况下，仍然有129664=82944种状态。若用穷举法求这类问题，将是不胜其烦的。,为此，我们必须寻找解决问题的更好途径。,对符合要求的方形柱体来讲，交换任意两个正方体的上下位置，得到的方形柱体仍是符合要求的，即它的4个侧面都有4种颜色。它的每一对对面由4个正方体各一个对面组成，因此问题的要素是4个正方体各3个对面的颜色的构成，于是从每个对面的着色考虑。用字母,b,g,r,y,分别表示蓝、绿、红、黄4种颜色，并作为图的4个 顶点，4个正方体的各三个对面依各对面的颜色连以边，并分别标以,e1、e2、e3、e4，,比如第一个正方体有一对面着蓝、黄两色，则从顶点,b,到,y,引一条边标以,e1,另两对面为红对红、红对绿，故联结,r,e,和,r,g,均标以,e1。,同样地根据第二、三、四正方体的各对面着色分别连以边并分别标以,e2、e3、e4。,则得图,G，,如图13所示。,【方形柱体堆砌问题分析】,e4,b,y,g,r,e1,e1,e1,e1,e2,e2,e2,e3,e3,e3,e4,e4,从图中，能找到两个,Hamiltion,回路，每个回路的4条边分别是,e1,e2,e3,e4。,(,见下页,),e4,b,y,g,r,e1,e1,e1,e2,e2,e2,e3,e3,e3,e4,e4,2.选择合适的理论体系,图由点、边、权三部分组成，根据这三部分的性质的不同，就有着不同的图论模型，有着不同的理论和算法，也就构成了不同的理论体系。图论建模依据的是图论的基本理论和基本算法。,例如二分图把整个点集,V,分为两个子集，规定子集内部的点之间没有边，因此二分图就有着不同于一般图的特殊性质，而它的匹配算法也就比一般图的算法简单；此外还有树、有向无环图等，它们属于不同的理论体系，有着各自不同的性质，适于用不同的算法求解。,权的加入使图论模型和求解目标变得更加复杂多样,有的权则表示容量或是流量，它们的运算特征是“,串联求最值，并联求和,”，即一条路径上最大或是最小的权决定了整条路径的权，而求解目标则是求图中或是两点之间所有路径的权的加和。,还有的图不仅包含边权（边集,E,到实数集,R,的映射），还包含点权（点集,V,到实数集,R,的映射）；或是包含好几类不同性质的权。,有的权表示长度或是时间等等，它们的运算特征是“,串联求和，并联求最值,”，即一条路径的权由这条路径上每条边的权相加得到，求解目标往往是求图中或是两点之间所有路径的权的最优值。,以上这些差异形成了图论模型的多样化，使图论模型可以广泛地适应各类问题，但这些丰富的选择同时也增加了图论建模的难度。,权的运算也会产生一些变形，例如权的运算由简单的相加、求最值扩展到相乘，或是更复杂的函数计算等等。,【例3】,机器人布阵,有一个,N*M(N,M=50),的棋盘，棋盘的每一格是三种类型之一：空地、草地、墙。机器人只能放在空地上。在同一行或同一列的两个机器人，若它们之间没有墙，则它们可以互相攻击。问给定的棋盘，最多可以放置多少个机器人，使它们不能互相攻击。,墙,Wall,草地,Grass,空地,Empty,【模型一】,在问题的原型中，草地，墙这些信息不是我们所关心的，我们关心的只是空地和空地之间的联系。因此，我们很自然想到了下面这种简单的模型：,以空地为顶点，有冲突的空地间连边，我们可以得到右边的这个图,：,问题的求解目标是寻,求图,G,的,最大独立集,，即求,G,的独立数,(G)。,一般图的,(G),是很难计算的，除非对于一些特殊的图。如完全图,K,n,的独立数为,n,二分完全图,Km,n,的独立数为,maxm,n。,显然这一模型不是属于一些特殊的图，给我们设计算法带来很大的麻烦。,【模型二】,我们将每一行，每一列被墙隔开，且包含空地的连续区域称作,“,块,”,。显然，在一个块之中，最多只能放一个机器人。我们把水平方向的这些块编上号；同样，把竖直方向的块也编上号。,1,2,3,4,5,1,2,3,4,水平方向的块编号,竖直方向的块编号,把每个横向块看作,X,部的点，竖向块看作,Y,部的点，若两个块有公共的空地，则在它们之间连边。于是，问题转化成这样的一个二分图：,由于每条边表示一个空地，有冲突的空地之间必有公共顶点，所以问题转化为二分图的最大匹配问题。,比较前面的两个模型：模型一过于简单，没有给问题的求解带来任何便利；模型二则充分抓住了问题的内在联系，巧妙地建立了二分图模型。为什么会产生这种截然不同的结果呢？其一是由于对问题分析的角度不同：模型一以空地为点，模型二以空地为边；其二是由于对原型中要素的选取有差异：模型一对要素的选取不充分，模型二则保留了原型中“棋盘”这个重要的性质。由此可见，要素的选取，分析角度的不同影响了理论体系的选择。这两点都是图论建模至关重要的步骤。,【例4】奇怪的数列,编程输入3个整数,n，p，q，,寻找一个由整数组成的数列（,a,1,，a,2,，a,n,），,要求：其中任意连续,p,项之和为正数，任意连续,q,项之和为负数。0,n100，0p，qn，,若不存在这样的整数数列，则输出,NO；,否则输出满足条件的一个数列即可。,【输入格式】,输入文件名为,num.in，,仅一行分别表示,n，p，q，,之间用一个空格隔开。,【输出格式】,输出文件名为,num.out，,只有一行，有解即输出这个数列，每个数之间用一个空格隔开。否则输出,NO。,【,奇怪的数列,分析】,从形式上看，这道题与图论风马牛不相干，题中既未出现图论中常见的“车站”，“城市”等顶点，也未出现“公路”，“铁路”等边，更未出现“长度”，“传输时间”等权。仅以数学角度考虑，按常规思想来分析如何表示“连续几项之和”这一要点，直接将第,i,个整数,a,i,开始的,k,个整数之和描述成多项式,a,i,+,a,i,+1,+,a,i,+k-1,的话，问题就很难再往下思考和解决了。所以，我们不防换个角度，暂且撇去每一项数究竟为何值的具体细节，而将注意力集中至连续性这一特点上。设,s,i,表示数列前,i,个整数之和，即,s,i,=a,1,+a,2,+,a,i,。,其中,s,0,=0(0in)。,显然根据题意，有：,s,i,s,i,+p,(0in-p),s,i,+q,s,j,(0i，jn)，,则从,s,i,往,s,j,引出一条有向边。例如对于,n=6，p=5，q=3,的情况，我们可以建立图4,S,1,S,0,S4,S2,S6,S5,S3,图4,【,奇怪的数列,分析】,构造这样的有向图很简单，过程如下：,fillchar,(g，,sizeof,(g)，0)；,有向图的邻接矩阵初始化,fillchar,(d，,sizeof,(d)，0)；,各顶点的入度序列初始化,for i：=0 to n do ,根据两组不等式构造有向图,begin,if i+p=n then begin,gi+p，i=1；,di=di+1；,end；,if i+q=n then begin,gi，i+q=1；,di+q=di+q+1；,end；,end；,【,奇怪的数列,分析】,显然，按照上面的定义，如果建立的图可以拓扑排序，其顶点的拓扑序列可以对应满足条件的整数数列；反之，不存在这样的整数数列。,算法框架为：,对图进行拓扑排序；,if,图有回路,then,无解退出,else,生成拓扑序列,order0ordern；,如果得到了一个拓扑序列，该如何转换成,s,数组呢？因为拓扑序列中顶点对应的,s,值是递减的，其中,s,0,=0。,如果,orderi=0，,则依次设定,s,order,0,=i，,s,order,1,=i-1，,s,order,i-1,=1，,s,order,i,=0，,s,order,i+1,=-1，,s,order,n,=i-n。,例如，对于图4所示的有向图，可以得到表1：,【,奇怪的数列,分析】,i,0,1,2,3,4,5,6,orderi,2,5,0,3,6,1,4,s,order,i,2,1,0,-1,-2,-3,-4,所以，得到,s,0,=0，s,1,=-3，s,2,=2，s,3,=-1，s,4,=-4，s,5,=1，s,6,=-2。,再根据,s,的定义，由：,a,i,=(a,0,+a,1,+,a,i,-1,+,a,i,)-(a,0,+a,1,+,a,i,-1,)=,s,i,-,s,i,-1,，,求出：,a,1,=s,1,-s,0,=-3，a,2,=s,2,-s,1,=5，a,3,=s,3,-s,2,=-3，a,4,=s,4,-s,3,=-3，a,5,=s,5,-s,4,=5，a,6,=s,6,-s,5,=-3。,显然这个整数数列的任意连续5个整数之和为正，任意连续3个整数之和为负。由拓扑序列构造整数数列的算法如下：,fillchar,(s，,sizeof,(s)，0)；,for i：=0 to n do,if orderi0 then for j：=i,downto,0 do sorderjsorderj+1,else break；,for j：=i+1 to n do sorderji-j；,for i：=1 to n do aisi-si-1；,通过以上分析可知，本题的关键还在于建模：把,s,i,作为顶点，,s,的大小关系作为边，并按照其递减顺序设定边的权值，应用拓扑排序这一经典算法很完美地解决了该题，这种创造性的构思在解题过程中起了关键性的作用。,三.模型的优化,建立图论模型是为了解决问题，但有时往往会遇到这样的情况：在建立起一个模型之后，却不知该如何分析、求解，或是发现建立起的模型无法表现原型的某些重要的性质等等。图论模型建立的过程，是一个不断完善的过程，在建模过程中，结合对问题更深层次的分析，结合算法设计，实现模型的优化。,【例5】障碍物探测车,有一个登陆舱（,POD）,里边装有许多障碍物探测车（,MEV），,将在火星表面登陆。着陆后，探测车离开登陆舱向相距不远的先期达到的传送器(,Transmitter),移动。,MEV,一边移动，一边采集岩石（,Rock）,标本，岩石由第一个访问到它的,MEV,采集，每块岩石只能被采集一次。但是这之后，.,问题可简述为：在,P,Q,的矩形中，每个格子的地形可能是下列三种之一：,（1）障碍：无法通过；,（2）平地：平坦无物，可通过；,（3）石块：可通过，第一次通过时可采到一块岩石；,求,M,条的路径（,M,给定），使得路径能够覆盖到石块数总和最大，路径要满足的条件是：,（1）每条路径都是从(1,1)到(,P,Q)，,途中每步只能向东或向南走一格；,（2）路径不通过障碍。,样例输入图示。（探测车数,M=2）,样例输出图示：(覆盖到石块数为3),【障碍物探测车分析】,1本题的难点就在于多辆探测车之间的配合问题，而对于只有一辆探测车的退化情况，应用动态规划可得到最优解:,用二维数组,map1.p,1.q 0f 0.2,表示火星表面情况：,mapi,j=0,表示位置（,i,j）,为平地；,mapi,j=1,表示位置（,i,j）,为障碍；,mapi,j=2,表示位置（,i,j）,为岩石。,设,Si,j,表示探测车从（1，1）位置移动到（,i,j）,位置所能够采集到的岩石标本数目的最大值。则有动态规划方程如下：,Si,j=,Maxsi-1,j,si.j-1,mapi,j=0;,0,mapi,j=1;(1ip,1jq),Maxsi-1,j,si.j-1+1;mapi,j=2;,边界条件：,si,0=0,s0,j=0 (1ip,1jq),2.当,m2,时，对,m,辆探测车各使用一次上述的动态规划算法，就可以得到一个较优解。由于这种简单的贪心没有顾及到各探测车之间的配合，所以不能保证得到最优解，如下面的例子：,以上两个算法都是基于一般意义 的图,GV,E,这一模型上考虑的，如果将一辆探测车的运动看作一条流，因为探测车的数目一定，所以总的流量是确定的。而解的优劣，即采集的标本数量的多少，就只能体现在单位流量的“费用”上了。因此选择使用最小费用最大流的方法求解。,3.网络流模型,将图,G,扩充为一个可以求解的网络模型：,（1）在建图时，可以略去所有障碍物位置，以及与(1,1)、(,p,q),不连通的位置，也可看作障碍物（探测车不会经过）。其余的位置（平地和岩石）都作为图,G,的顶点。,顶点集,V=Vi,j1ip,1jq,mapi,j1；,有向边集,E=,vi,j,vi+1,jvi,jV,vi+1,jV vi,j,vi,j+1vi,jV,vi,j+1V。,（2）根据题意再把图,G,扩充为 网络,N=V,E,C,R,C,代表网络中各边的容量，,R,代表各边上单位流量的费用。由于探测车的移动路线可以任意重叠，所以这些边的容量,C=，,费用,R=2。,（3）如何体现“采集岩石标本”的特征，对于岩石顶点，先到的探测车采到标本，对后到的探测车来说就是平地，一个顶点怎样来扮演两种不同的角色？我们把岩石顶点,Vi,j,分出一个顶点,VI,j,并增加 3条边：,1)边,Vij,Vij，,容量,C(Vij,Vij)=1,表示标本只能采集一次，费用,R(Vij,Vij,)=0;,2),边,Vij,Vij+1,和边,Vij,Vi+1j，,容量都是1，费用都是1。,这样，每采集一块岩石，对应的流的代价就会减少1；同时，受容量的限制，每块岩石也最多被采集一次。,（4）最后再为网络添加源点和汇点：因为,m,辆探测车都从（1，1）出发，所以源点,s,只引出一条边,s,V1,1,容量为,费用为0；类似，如果,mapp,q=0,即（,p,q）,处是平地，则汇点,t,也只引入一条边,Vp,q,t,容量为，费用为0；如果,mapp,q=2,即该处是岩石，则多引一条边,Vp,q,t,容量为1，费用也为1。,这样就完成了使用最小费用最大流算法的建模。,四.结束语,以上分析了图论模型建立中的两个要点和图论模型优化的方法。在实际的建模过程中，它们是密不可分的：正确提取原型中的要素；对应到特定理论体系中相应的元素上；建立起初步的模型；然后根据需要进行适当的优化。至此，一个适于求解的图论模型才建立成功。在这其中，无论是对建模原则的把握，还是模型优化方法的运用，都遵循着一点：原型本身的性质决定了模型。如果硬要把原型套到不合适的模型上去，往往反而会破坏原型的关键性质，这时，即使建立的模型再怎么巧妙、经典，也是经不住考验的。,图论算法和理论十分独特精妙，图论模型的建立和优化十分灵活。因此，对图论模型的研究并非一朝一夕的事，需要持之以恒。,独立集概念在图,G,中，选其中的一些顶点构成一个集合,U，,如果集合,U,中任意两个顶点在,G,中不相邻，称,U,是图,G,的一个独立集。对于独立集,U,任意再增加一个顶点就破坏它的独立性，则称这独立集为,G,的一个极大独立集。极大独立集不是唯一的，而且连顶点数都不尽相同。顶点数最多的极大独立集，称其为最大独立集。（下图有两个独立集且都是极大独立集）,墙,Wall,草地,Grass,空地,Empty,