图论模型的构建.doc

。1736年数学家欧拉(Euler1707—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到顶点φ的最短路径问题。Mwsvmwsmwvmsvms图1-1渡河问题Mvwsvφ【例2】方形柱体堆砌有4个正立方体,它们的6个侧面各着以绿、蓝、红、黄4种颜色之一,如图1-2所示。现在要把这4个正方体堆成一方形柱体,堆成的方形柱体每个侧面4种颜色都有。求解任务:1、这4个正方体能否堆成符合要求的方形柱体?2、若能,找出一种堆砌方法。【分析】一个正方体有6个面,所以4个正方体可以堆砌出为数十分可观的不同状态。就是确定了4个正方体依Ⅰ,Ⅱ,Ⅲ,Ⅳ次序从上到下排列,只考虑两两接触面不同,也有64=1296种排列,这里还没有考虑4个侧面的不同组合。若考虑到后者,又会衍生出许多各异的形式,先令第Ⅰ个正方体保持不动,Ⅱ,Ⅲ,Ⅳ正方体个有4个侧面,故有43=64种状态。因此即使在从上到下按序排列情况下,仍然有1296×64=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,如图1—3所示。从图1---3中,能找到两个Hamiltion回路,每个回路的4条边分别是e1,e2,e3,e4。如图1---4所示。每一回路正好对应方形柱体一对对面的颜色分布,这便得到了本题的解。、边、权三部分组成,根据这三部分的性质的不同,就有着不同的图论模型,有着不同的理论和算法,也就构成了不同的理论体系。图论建模依据的是图论的基本理论和基本算法。例如二分图把整个点集V分为两个子集,规定子集内部的点之间没有边,因此二分图就有着不同于一般图的特