图论模型的构建.ppt
《图论模型的构建.ppt》由会员分享,可在线阅读,更多相关《图论模型的构建.ppt(41页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、图论模型的构建江苏省苏州中学 章维铣一绪言一绪言 图论是数学的一个有趣的分支。图论是数学的一个有趣的分支。17361736年数学家欧年数学家欧拉(拉(EulerEuler 1707 170717831783)发表了一篇论文,用图的方发表了一篇论文,用图的方法解决了著名的七桥问题,是图论建模的经典例子。法解决了著名的七桥问题,是图论建模的经典例子。图论建模是指对一些客观事物进行抽象、化简,图论建模是指对一些客观事物进行抽象、化简,并用图来描述事物特征及内在联系的过程,就是抓住并用图来描述事物特征及内在联系的过程,就是抓住问题的本质,把问题抽象为点、边、权的关系。建立问题的本质,把问题抽象为点、边
2、、权的关系。建立图论模型的目的和建立其它的数学模型一样,都是为图论模型的目的和建立其它的数学模型一样,都是为了简化问题,突出要点,以便更深入地研究问题的本了简化问题,突出要点,以便更深入地研究问题的本质;它的求解目标可以是最优化问题,也可以是存在质;它的求解目标可以是最优化问题,也可以是存在性或是构造性问题。许多看似无从入手的问题,通过性或是构造性问题。许多看似无从入手的问题,通过图论建模,往往能转化为我们熟悉的经典问题。图论建模,往往能转化为我们熟悉的经典问题。二图论建模方法二图论建模方法1.要素的选取要素的选取 在建立模型之前,我们首先要对研究对象进在建立模型之前,我们首先要对研究对象进行
3、全面的调查,将原型理想化、简单化;然后对行全面的调查,将原型理想化、简单化;然后对原型进行初步的分析,分清其中的各个要素及求原型进行初步的分析,分清其中的各个要素及求解目标,理出它们之间的联系;下一步就是用恰解目标,理出它们之间的联系;下一步就是用恰当的模型来描述这些要素及联系。当的模型来描述这些要素及联系。【例1】渡河问题渡河问题 一个人带了一只狼、一只羊和一筐白菜想要过河。河上有一只小船,每次除了人以外,只能带一样东西。另外,如果人不在时狼就会吃掉羊,羊就要吃白菜。问怎样安排渡河,才能做到既把所有东西都带过河,而且在河上往返次数最少?问题的要素有三点:(1)人及他所带的3样东西;(2)人不
4、在时狼就会吃掉羊,羊就要吃白菜,即人在渡河时,一岸上不能同时留下狼和羊或羊和白菜;(3)人每次至多带一样东西渡河,并要保证岸上的安全。问题的求解目标:求河上往返次数最少的渡河方案。对于要素(1),用字母m代表人,w代表狼,s代表羊,v代表白菜。要素(2)、(3)可抽象为开始时设人和其他三样东西在河的左岸,这种情况用集合mwsv表示。在过河过程中左岸出现的情况有以下16种:wmsv mws mwv msv wsv mw ms mvws wv sv m s v w 剔除下述6种可能发生狼吃羊,羊吃白菜的情况:(注意照顾右岸的情况)wsv ws sv mw mv m将剩下的10种情况作为图G的顶点,
5、图G的边是按下述规则来连接的:如果情况A经过一次渡河可以变成情况B,就在情况A与情况B之间连一条边。根据这一规则,构造的图G如下面所示:问题的求解目标就归结为:在图G中找一条连接顶点mwsv与,并且包含边数最少的路径。把图的边长设为1,那么渡河问题归结为求顶点mwsv到顶点的最短路径问题。【例【例2 2】方形柱体堆砌】方形柱体堆砌 有4个正立方体,它们的6个侧面各着以绿、蓝、红、黄4种颜色之一,如图1-2所示。现在要把这4个正方体堆成一方形柱体,堆成的方形柱体每个侧面4种颜色都有。求解任务:1、这4个正方体能否堆成符合要求的方形柱体?2、若能,找出一种堆砌方法。【方形柱体堆砌问题分析方形柱体堆
6、砌问题分析】一个正方体有6个面,所以4个正方体可以堆砌出为数十分可观的不同状态。就是确定了4个正方体依,次序从上到下排列,只考虑两两接触面不同,也有64=1296种排列,这里还没有考虑4个侧面的不同组合。若考虑到后者,又会衍生出许多各异的形式,先令第个正方体保持不动,正方体个有4个侧面,故有43=64种状态。因此即使在从上到下按序排列情况下,仍然有129664=82944种状态。若用穷举法求这类问题,将是不胜其烦的。为此,我们必须寻找解决问题的更好途径。为此,我们必须寻找解决问题的更好途径。对符合要求的方形柱体来讲,交换任意两个正方体的上下位置,得到的方形柱体仍是符合要求的,即它的4个侧面都有
7、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所示。【方形柱体堆砌问题分析】【方形柱体堆砌问题分析】e4bygre1e1e1e1e2e2e
8、2e3e3e3e4e4从图中,能找到两个Hamiltion回路,每个回路的4条边分别是 e1,e2,e3,e4。(见下页)e4bygre1e1e1e2e2e2e3e3e3e4e42.2.选择合适的理论体系选择合适的理论体系 图由点、边、权三部分组成,根据这三部分的性图由点、边、权三部分组成,根据这三部分的性质的不同,就有着不同的图论模型,有着不同的理论质的不同,就有着不同的图论模型,有着不同的理论和算法,也就构成了不同的理论体系。图论建模依据和算法,也就构成了不同的理论体系。图论建模依据的是图论的基本理论和基本算法。的是图论的基本理论和基本算法。例如二分图把整个点集例如二分图把整个点集V分为两
9、个子集,规定子分为两个子集,规定子集内部的点之间没有边,因此二分图就有着不同于一集内部的点之间没有边,因此二分图就有着不同于一般图的特殊性质,而它的匹配算法也就比一般图的算般图的特殊性质,而它的匹配算法也就比一般图的算法简单;此外还有树、有向无环图等,它们属于不同法简单;此外还有树、有向无环图等,它们属于不同的理论体系,有着各自不同的性质,适于用不同的算的理论体系,有着各自不同的性质,适于用不同的算法求解。法求解。权的加入使图论模型和求解目标变得更加复杂多样 有的权则表示容量或是流量,它们的运算特征是有的权则表示容量或是流量,它们的运算特征是“串联求最值,并联求和串联求最值,并联求和”,即一条
10、路径上最大或是最小,即一条路径上最大或是最小的权决定了整条路径的权,而求解目标则是求图中或是的权决定了整条路径的权,而求解目标则是求图中或是两点之间所有路径的权的加和。两点之间所有路径的权的加和。还有的图不仅包含边权(边集还有的图不仅包含边权(边集E E到实数集到实数集R R的映的映射),还包含点权(点集射),还包含点权(点集V V到实数集到实数集R R的映射);或是包的映射);或是包含好几类不同性质的权。含好几类不同性质的权。有的权表示长度或是时间等等,它们的运算特有的权表示长度或是时间等等,它们的运算特征是征是“串联求和,并联求最值串联求和,并联求最值”,即一条路径的权由这,即一条路径的权
11、由这条路径上每条边的权相加得到,求解目标往往是求图中条路径上每条边的权相加得到,求解目标往往是求图中或是两点之间所有路径的权的最优值。或是两点之间所有路径的权的最优值。以上这些差异形成了图论模型的多样化,使图论模型可以广泛地适应各类问题,但这些丰富的选择同时也增加了图论建模的难度。权的运算也会产生一些变形,例如权的运算由简权的运算也会产生一些变形,例如权的运算由简单的相加、求最值扩展到相乘,或是更复杂的函数计单的相加、求最值扩展到相乘,或是更复杂的函数计算等等。算等等。【例3】机器人布阵机器人布阵有一个N*M(N,M=50)的棋盘,棋盘的每一格是三种类型之一:空地、草地、墙。机器人只能放在空地
12、上。在同一行或同一列的两个机器人,若它们之间没有墙,则它们可以互相攻击。问给定的棋盘,最多可以放置多少个机器人,使它们不能互相攻击。墙 Wall草地 Grass 空地 Empty【模型一】在问题的原型中,草地,墙这些信息不是我们所关心的,我们关心的只是空地和空地之间的联系。因此,我们很自然想到了下面这种简单的模型:以空地为顶点,有冲突的空地间连边,我们可以得到右边的这个图:问题的求解目标是寻求图G的最大独立集,即求G的独立数(G)。一般图的(G)是很难计算的,除非对于一些特殊的图。如完全图K Kn的独立数为n,二分完全图Km,n的独立数为maxm,n。显然这一模型不是属于一些特殊的图,给我们设
13、计算法带来很大的麻烦。【模型二】我们将每一行,每一列被墙隔开,且包含空地的连续区域称作“块”。显然,在一个块之中,最多只能放一个机器人。我们把水平方向的这些块编上号;同样,把竖直方向的块也编上号。123451234水平方向的块编号竖直方向的块编号把每个横向块看作X部的点,竖向块看作Y部的点,若两个块有公共的空地,则在它们之间连边。于是,问题转化成这样的一个二分图:由于每条边表示一个空地,有冲突的空地之间必有公共顶点,所以问题转化为二分图的最大匹配问题。比较前面的两个模型:模型一过于简单,比较前面的两个模型:模型一过于简单,没有给问题的求解带来任何便利;模型二则充没有给问题的求解带来任何便利;模
14、型二则充分抓住了问题的内在联系,巧妙地建立了二分分抓住了问题的内在联系,巧妙地建立了二分图模型。为什么会产生这种截然不同的结果呢图模型。为什么会产生这种截然不同的结果呢?其一是由于对问题分析的角度不同:模型一?其一是由于对问题分析的角度不同:模型一以空地为点,模型二以空地为边;其二是由于以空地为点,模型二以空地为边;其二是由于对原型中要素的选取有差异:模型一对要素的对原型中要素的选取有差异:模型一对要素的选取不充分,模型二则保留了原型中选取不充分,模型二则保留了原型中“棋盘棋盘”这个重要的性质。由此可见,要素的选取,分这个重要的性质。由此可见,要素的选取,分析角度的不同影响了理论体系的选择。这
15、两点析角度的不同影响了理论体系的选择。这两点都是图论建模至关重要的步骤。都是图论建模至关重要的步骤。【例【例4 4】奇怪的数列】奇怪的数列 编编程程输输入入3 3个个整整数数n n,p p,q q,寻寻找找一一个个由由整整数数组组成成的的数数列列(a a1 1,a a2 2,a an n),要要求求:其其中中任任意意连连续续p p项项之之和和为为正正数数,任任意意连连续续q q项项之之和和为为负负数数。00n100n100,0p0p,qnqn,若若不不存存在在这这样样的的整整数数数数列列,则则输输出出NONO;否否则则输输出出满满足足条条件件的的一一个数列即可。个数列即可。【输入格式】【输入格
16、式】输输入入文文件件名名为为num.innum.in,仅仅一一行行分分别别表表示示n n,p p,q q,之之间间用用一个空格隔开。一个空格隔开。【输出格式】【输出格式】输输出出文文件件名名为为num.outnum.out,只只有有一一行行,有有解解即即输输出出这这个个数数列列,每个数之间用一个空格隔开。否则输出每个数之间用一个空格隔开。否则输出NONO。【奇怪的数列奇怪的数列分析】从从形形式式上上看看,这这道道题题与与图图论论风风马马牛牛不不相相干干,题题中中既既未未出出现现图图论论中中常常见见的的“车车站站”,“城城市市”等等顶顶点点,也也未未出出现现“公公路路”,“铁铁路路”等等边边,更
17、更未未出出现现“长长度度”,“传传输输时时间间”等等权权。仅仅以以数数学学角角度度考考虑虑,按按常常规规思思想想来来分分析析如如何何表表示示“连连续续几几项项之之和和”这这一一要要点点,直直接接将将第第i i个个整整数数a ai i开开始始的的k k个个整整数数之之和和描描述述成成多多项项式式a ai i+a ai i+1+1+a ai i+k-1+k-1的的话话,问问题题就就很很难难再再往往下下思思考考和和解解决决了了。所所以以,我我们们不不防防换换个个角角度度,暂暂且且撇撇去去每每一一项项数数究究竟竟为为何何值值的的具具体体细细节节,而而将将注注意意力力集集中中至至连连续续性性这这一一特特
18、点点上上。设设s si i表表示示数数列列前前i i个个整整数数之之和和,即即s si i=a=a1 1+a+a2 2+a ai i。其中其中s s0 0=0(0in)=0(0in)。显然根据题意,有:显然根据题意,有:s si i s si i+p+p (0in-p)(0in-p)s si i+q+q s sj j(0i(0i,jn)jn),则则从从s si i往往s sj j引引出出一一条条有有向向边边。例例如如对对于于n=6n=6,p=5p=5,q=3q=3的的情情况况,我我们可以建立图们可以建立图4 4S1S0S4S2S6S5S3图4【奇怪的数列奇怪的数列分析】构造这样的有向图很简单,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 模型 构建
限制150内