图论模型的构建.doc

图论模型的构建 章维铣图论模型的构建一绪言图论是数学的一个有趣的分支。1736年数学家欧拉（Euler 17071783）发表了一篇论文，用图的方法解决了著名的七桥问题，是图论建模的经典例子。图论建模是指对一些客观事物进行抽象、化简，并用图来描述事物特征及内在联系的过程，就是抓住问题的本质，把问题抽象为点、边、权的关系。建立图论模型的目的和建立其它的数学模型一样，都是为了简化问题，突出要点，以便更深入地研究问题的本质；它的求解目标可以是最优化问题，也可以是存在性或是构造性问题。许多看似无从入手的问题，通过图论建模，往往能转化为我们熟悉的经典问题。本文是在读者已经对图论的基础知识和基本算法有所了解的前提下展开有关图论建模的讨论，通过一些典型信息学竞赛试题的分析，达到举一反三、触类旁通的目的。二图论建模方法在建立模型之前，我们首先要对研究对象进行全面的调查，将原型理想化、简单化；然后对原型进行初步的分析，分清其中的各个要素及求解目标，理出它们之间的联系；下一步就是用恰当的模型来描述这些要素及联系。1. 要素的选取【例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到顶点的最短路径问题。Mwsv mws mwv msv ms图1-1渡河问题Mv w s v 【例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所示。从图1-3中，能找到两个Hamiltion回路，每个回路的4条边分别是e1,e2,e3,e4。如图1-4所示。每一回路正好对应方形柱体一对对面的颜色分布，这便得到了本题的解。2. 选择合适的理论体系图由点、边、权三部分组成，根据这三部分的性质的不同，就有着不同的图论模型，有着不同的理论和算法，也就构成了不同的理论体系。图论建模依据的是图论的基本理论和基本算法。例如二分图把整个点集V分为两个子集，规定子集内部的点之间没有边，因此二分图就有着不同于一般图的特殊性质，而它的匹配算法也就比一般图的算法简单；此外还有树、有向无环图等，它们属于不同的理论体系，有着各自不同的性质，适于用不同的算法求解。而权的加入则使图论模型和求解目标变得更加复杂多样了。有的权表示长度或是时间等等，它们的运算特征是“串联求和，并联求最值”，即一条路径的权由这条路径上每条边的权相加得到，求解目标往往是求图中或是两点之间所有路径的权的最优值。有的权则表示容量或是流量，它们的运算特征是“串联求最值，并联求和”，即一条路径上最大或是最小的权决定了整条路径的权，而求解目标则是求图中或是两点之间所有路径的权的加和。以上只是基本的几类权，它们还会产生一些变形，例如权的运算由简单的相加、求最值扩展到相乘，或是更复杂的函数计算等等。还有的图不仅包含边权（边集E到实数集R的映射），还包含点权（点集V到实数集R的映射）；或是包含好几类不同性质的权。以上这些差异形成了图论模型的多样化，使图论模型可以广泛地适应各类问题，但这些丰富的选择同时也增加了图论建模的难度。对于有些题目，我们可能很自然地就联想到某种图论模型，例如看到表达式，就会联想起表达式树；但对于另一些题目，分析的角度不同，就会得出不同的模型，产生不同的效果。【例3】 机器人布阵墙 Wall草地 Grass 空地 Empty有一个N*M(N,M=50)的棋盘，棋盘的每一格是三种类型之一：空地、草地、墙。机器人只能放在空地上。在同一行或同一列的两个机器人，若它们之间没有墙，则它们可以互相攻击。问给定的棋盘，最多可以放置多少个机器人，使它们不能互相攻击。【模型一】在问题的原型中，草地，墙这些信息不是我们所关心的，我们关心的只是空地和空地之间的联系。因此，我们很自然想到了下面这种简单的模型：以空地为顶点，有冲突的空地间连边，我们可以得到右边的这个图：问题的求解目标是寻求图G的最大独立集，即求G的独立数(G)。一般图的(G)是很难计算的，除非对于一些特殊的图。如完全图Kn的独立数为n,二分完全图Km,n的独立数为maxm,n。（附：独立集概念在图G中，选其中的一些顶点构成一个集合U，如果集合U中任意两个顶点在G中不相邻，称U是图G的一个独立集。对于独立集 U,任意再增加一个顶点就破坏它的独立性，则称这独立集为G的一个极大独立集。极大独立集不是唯一的，而且连顶点数都不尽相同。顶点数最多的极大独立集，称其为最大独立集。（下图有两个独立集且都是极大独立集）显然这一模型不是属于一些特殊的图，给我们设计算法带来很大的麻烦。123451234水平方向的块编号竖直方向的块编号【模型二】我们将每一行，每一列被墙隔开，且包含空地的连续区域称作“块”。显然，在一个块之中，最多只能放一个机器人。我们把水平方向的这些块编上号；同样，把竖直方向的块也编上号。把每个横向块看作X部的点，竖向块看作Y部的点，若两个块有公共的空地，则在它们之间连边。于是，问题转化成这样的一个二分图：由于每条边表示一个空地，有冲突的空地之间必有公共顶点，所以问题转化为二分图的最大匹配问题。比较前面的两个模型：模型一过于简单，没有给问题的求解带来任何便利；模型二则充分抓住了问题的内在联系，巧妙地建立了二分图模型。为什么会产生这种截然不同的结果呢？其一是由于对问题分析的角度不同：模型一以空地为点，模型二以空地为边；其二是由于对原型中要素的选取有差异：模型一对要素的选取不充分，模型二则保留了原型中“棋盘”这个重要的性质。由此可见，要素的选取，分析角度的不同影响了理论体系的选择。这两点都是图论建模至关重要的步骤。【例4】奇怪的数列编程输入3个整数n，p，q，寻找一个由整数组成的数列（a1，a2，an），要求：其中任意连续p项之和为正数，任意连续q项之和为负数。0n100，0p，qn，若不存在这样的整数数列，则输出NO；否则输出满足条件的一个数列即可。【输入格式】 输入文件名为num.in，仅一行分别表示n，p，q，之间用一个空格隔开。【输出格式】 输出文件名为num.out，只有一行，有解即输出这个数列，每个数之间用一个空格隔开。否则输出NO。【输入输出样例】num.in6 5 3num.out-3 5 -3 -3 5 -3num.in3 2 1num.outNO【分析】从形式上看，这道题与图论风马牛不相干，题中既未出现图论中常见的“车站”，“城市”等顶点，也未出现“公路”，“铁路”等边，更未出现“长度”，“传输时间”等权。仅以数学角度考虑，按常规思想来分析如何表示“连续几项之和”这一要点，直接将第i个整数ai开始的k个整数之和描述成多项式ai+ai+1+ai+k-1的话，问题就很难再往下思考和解决了。所以，我们不防换个角度，暂且撇去每一项数究竟为何值的具体细节，而将注意力集中至连续性这一特点上。设si表示数列前i个整数之和，即si=a1+a2+ai。其中s0=0 (0in)。显然根据题意，有： sisi+p (0in-p) si+qsj(0i，jn)，则从si往sj引出一条有向边。例如对于n=6，p=5，q=3的情况，我们可以建立图4S1S0S4S2S6S5S3图4构造这样的有向图很简单，过程如下： fillchar(g，sizeof(g)，0)； 有向图的邻接矩阵初始化 fillchar(d，sizeof(d)，0)； 各顶点的入度序列初始化 for i：=0 to n do 根据两组不等式构造有向图 begin if i+pn then begin gi+p，i1；didi+1；end； if i+qn then begin gi，i+q1；di+qdi+q+1；end； end；显然，按照上面的定义，如果建立的图可以拓扑排序，其顶点的拓扑序列可以对应满足条件的整数数列；反之，不存在这样的整数数列。算法框架为： 对图进行拓扑排序； if 图有回路 then 无解退出 else 生成拓扑序列order0ordern；如果得到了一个拓扑序列，该如何转换成s数组呢？因为拓扑序列中顶点对应的s值是递减的，其中s0=0。如果orderi=0，则依次设定sorder0=i，sorder1=i-1，sorderi-1=1，sorderi=0，sorderi+1=-1，sordern=i-n。例如，对于图4所示的有向图，可以得到表1：表1i0123456orderi2503614sorderi210-1-2-3-4所以，得到s0=0，s1=-3，s2=2，s3=-1，s4=-4，s5=1，s6=-2。再根据s的定义，由： ai=(a0+a1+ai-1+ai) - (a0+a1+ai-1)=si-si-1 ，求出：a1=s1-s0=-3，a2=s2-s1=5，a3=s3-s2=-3，a4=s4-s3=-3，a5=s5-s4=5，a6=s6-s5=-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；通过以上分析可知，本题的关键还在于建模：把si作为顶点，s的大小关系作为边，并按照其递减顺序设定边的权值，应用拓扑排序这一经典算法很完美地解决了该题，这种创造性的构思在解题过程中起了关键性的作用。三. 模型的优化建立图论模型是为了解决问题，但有时往往会遇到这样的情况：在建立起一个模型之后，却不知该如何分析、求解，或是发现建立起的模型无法表现原型的某些重要的性质等等。图论模型建立的过程，是一个不断完善的过程，在建模过程中，结合对问题更深层次的分析，结合算法设计，实现模型的优化。【例5】障碍物探测车有一个登陆舱（POD）,里边装有许多障碍物探测车（MEV），将在火星表面登陆。着陆后，探测车离开登陆舱向相距不远的先期达到的传送器(Transmitter)移动。MEV一边移动，一边采集岩石（Rock）标本，岩石由第一个访问到它的 MEV采集，每块岩石只能被采集一次。但是这之后， .【分析】问题可简述为：在PQ的矩形中，每个格子的地形可能是下列三种之一：（1）障碍：无法通过；（2）平地：平坦无物，可通过；（3）石块：可通过，第一次通过时可采到一块岩石；求M条的路径（M给定），使得路径能够覆盖到石块数总和最大，路径要满足的条件是：（1）每条路径都是从(1,1)到(P,Q)，途中每步只能向东或向南走一格；（2）路径不通过障碍。下图是样例输入的图示。（探测车数M=2）样例输出的图示为：下面我们结合算法设计讨论本题的模型建立。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=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)设Si,j表示探测车从（1，1）位置移动到（i,j）位置所能够采集到的岩石标本数目的最大值。则有动态规划方程如下：2.当m2时，对 m辆探测车各使用一次上述的动态规划算法，就可以得到一个较优解。由于这种简单的贪心没有顾及到各探测车之间的配合，所以不能保证得到最优解，如下面的例子：3.网络流模型以上两个算法都是基于一般意义 的图GV,E这一模型上考虑的，如果将一辆探测车的运动看作一条流，因为探测车的数目一定，所以总的流量是确定的。而解的优劣，即采集的标本数量的多少，就只能体现在单位流量的“费用”上了。因此选择使用最小费用最大流的方法求解。将图G扩充为一个可以求解的网络模型：（1）在建图时，可以略去所有障碍物位置，以及与(1,1)、(p,q)不连通的位置，也可看作障碍物（探测车不会经过）。其余的位置（平地和岩石）都作为图G的顶点。顶点集V=Vi,j1ip,1jp,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代表各边上单位