图论模型的构建

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,图论模型的构建,江苏省苏州中学 章维铣,一绪言,图论是数学的一个有趣的分支。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个整数之和为负。由拓扑序列构造整数数列的算法