图论模型(看一笔画).ppt
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《图论模型(看一笔画).ppt》由会员分享,可在线阅读,更多相关《图论模型(看一笔画).ppt(53页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、第九章 图论模型在生产生活中,人们常常用图或网络来刻画、解释和处理某些实际问题,常见的如车辆流通图、电路网络图、赛事安排图和工程进度管理图等.这种表示方式不仅使实际问题变得直观、简洁、明了,而且也为实际问题的研究提供了一种有效的方法.近几十年来,随着运筹学、信息论和计算机科学的发展,人们对图论和网络的研究也越来越广泛和深入,并且迅速地产生了一门新兴的数学分支图论.在这一章里,我们将简略地介绍一些与此有关的实际问题以及解决这些问题的巧妙方法.9.1 一笔画问题9.1.1 七桥问题 18世纪,东普鲁士的哥尼斯堡是一座景致迷人的城市,普勒格尔河横贯其境,并在这儿形成两条支流,把整座城市分割成4个区域
2、(如图)ABCD哥尼斯堡七桥示意图哥尼斯堡七桥示意图河的两岸(C和D),河中的岛(A)和两条支流之间的半岛(B).当时有7座桥横跨普勒格尔河及其支流,把河岸、半岛和河心岛连接起来.有趣的桥群和哥城4区域的的迷人景色吸引了众多的的游客.有人在游览时提出这样的问题:能否从某个地方出发,穿过所有的桥各一次后再回到出发点?很多人做了尝试,但没有一个人成功.是否存在成功的可能性呢?人们既拿不出成功的方案,又找不到否定的理由.后来这个令人困惑的问题被年轻的瑞士数学家欧拉(Leonhard Eular)知道了,他在1736年向圣彼得堡学院递交的一篇论文中巧妙的解决了这个问题.他是怎么解决这个问题的呢?他首先
3、把哥尼斯堡的4个区域分别用A,B,C,D表示,7座桥表示成7条连接这4个点的线,于是哥尼斯堡七桥的情形就转化为下图的情形ABDC七桥问题模拟图七桥问题模拟图这个由4个点和7条连线(也叫边)组成.问题相应地变为:在上述模拟图中,从A,B,C,D中任何一点出 发,笔不离纸,但又不能重复任何一条边地画出模拟图,且起点与终点重合,这样的画法存在吗?这就是众所周知的“一笔画”问题.接下来,欧拉研究了能够“一笔画”的图形所应具有的性质.他注意到,这类图中的点倘若不是“一笔画”的起点和终点,那它作为“一笔画”的“中途点”应该具有这样的特性:笔沿着某条边“进入”点后,必定要沿着另一条边“出去”.于是,“中途点
4、”的边必定成对出现.也就是说,与“中途点”相连的边的条数必是偶数.我们把与点v相连接的边的条数称为该点的度数,记作d(v).d(v)为偶数时,点v称为偶点,否则称为奇点.按欧拉的分析,能“一笔画”的图的“中途点”的度数为偶点,而奇点只能作为“一笔画”的起点或终点.当起点和终点重合时,该图不存在奇点.概括起来,就是这样一个结论:如果一个图形可以“一笔画”,那么其奇点个数必为0(起点和终点重合)或2(起点和终点不重合).9.1.2 有关图的基本概念 为了便于说明,我们简要的介绍一下图的基本概念及其性质.我们经常遇到这样一些问题,他们仅包含两方面的内容:一是一些“对象”(如七桥问题中的岛和河岸),二
5、是这些对象之间的某种关系(如岛与岛、岛和河岸之间是否有桥连接,有几座桥连接).为表示这些对象和它们之间的关系,可以在纸上画一些点,每一点代表一个对象,称这些点为顶点,如果两个对象之间有所讨论的关系,就在相应的两点之间连一条线,这些线称为边,这样有若干个点和若干条边就构成了一个图.由若干个不同的顶点与连接其中某些顶点的边所组成的图形称为图.通常用G来表示图.用V表示图中所有顶点的集合,用 E表示所有边的集合,并且记为G=(V,E).图G中顶点的个数|V|称为G的阶.图的基本性质:设G是n阶图,则G中n个顶点的度数之和等于边数的两倍.证明:所有顶点的度数之和表示以每一顶点为端点的边的总数.由于一条
6、边有两个端点,因此每条边在顶点的度数之和中都被记入两次,所以顶点的度之和应为边数的两倍.推论:对于任意的图G,奇点的个数是偶数.在图G中,有一个不同的边组成的序列:e1,e2,em,如果其中边,ei=(vi-1,vi),i=1,2,3m.则称这个序列是从v0到vm的链.如果一条链的始点v0和终点vm重合,则称这条链为圈.如果对于图G中的任意两个顶点u和v,都有一条从u到v的链,则称这样的图G是连通的,否则称G是不连通的.经过图G的每条边的链,称为G的欧拉链.经过图G的每条边的圈称为G的欧拉圈.一个图若包含欧拉圈,则称这个图为欧拉图.直观的讲,欧拉图就是从某一顶点出发而每边恰通过一次又能回到出发
7、点的图.9.1.3 一笔画定理及其证明 在七桥问题的讨论中,我们得到了一个结论:如果一个图形可以“一笔画”,当且仅当其奇点个数必为0或2.那么我们自然会问,这个命题的逆命题成立吗?也就是说,当一个图形的奇点个数为0或2时,它可以“一笔画”吗?如果能画,是否有一种一般可行的画法?答案是肯定的.将原命题与其逆命题综合起来,就是我们所说的一笔画定理.一笔画定理:图G是欧拉链(即可以一笔画)的充要条件是:G是连通的,并且奇点的个数为0或2.当且仅奇点个数等于0时,连通图G是一个圈.证明 必要性:如果图G是一条从v1到vn+1的链,那么每一个不同于v1及vn+1的顶点vi(i=2,3你)都是偶顶点。故G
8、至多有两个奇点,即v1与vn+1。若G是圈,则v1与vn+1也是偶定点.充分性:如果G是连同,且奇顶点的个数为0,那么G一定是一个圈.事实上,从G中任一顶点v0出发,经相邻的边e1进入 V1,因为d(v1)是偶数,由v1再经相邻的边e2可进入v2,如此继续下去,每条边仅取一次,经过若干步后必可回到v0,于是就得到一个圈u1:v0v1v0.如果u恰好是图G,则命题得证.否则在图G中去条u1后得子图G1,G1中每个顶点也都是偶顶点.因图G是连通的,所以在G1中必定存在一个和u1公共的顶点u,使得G1中存在一个从u出发到u 的圈u2.于是u1和u2合起仍是一个圈.重复上述过程,因为G中总共只有有限条
9、边,总有一个时候,得到的这些圈恰好是图G.所以G是欧拉图.如果G连通,其奇顶点的个数为2,不妨设u和v是两个奇顶点.在u和v之间连一条边e得图G,于是G中奇顶点的个数为0,故G是一个圈,从而去掉e后,G便是一条欧拉链.证毕.注:在充分性的证明过程中,我们提供了”一笔画“的一种方法,即一笔画图形是由具有公共顶点的一个一个圈组合而成的,而且一个图能够”一笔画“的方法往往有很多种.9.1.4 一笔画定理的简单应用 回过头来看哥尼斯堡七桥问题。有模拟图知:d(A)=d(B)=d(D)=3,d(C)=5.4个顶点都是奇点,所以模拟图不可能被一笔画成.也就是说,哥尼斯堡七桥问题中要找的那条道路是不存在的.
10、9.1.5 评注在这个模型中,不需要考虑点线的长短大小,也不需要涉及量的计算,而只要研究点与点的关系就可以了.这种特殊的研究对象、研究方法和研究模型被公认为是图论学科的起源,现在以体现出它广泛的应用价值.9.2 中国邮递员问题 邮路问题:一个邮递员每次上班,要走遍他负责的每条路,然后回到邮局.问他应该怎么走才能使所走的路程最短?首先考虑这样一个问题:如图,每条线上的数字表示距离,小圆圈中的数字表示交叉路口的编号.我们从一点出发,有没有可能沿每条路都走过一遍(不许重复也不许遗漏),然后回到出发点呢?由于这一问题是我国管梅谷教授1960年首先提出的,所以国际上称之为中国邮递员问题。1234567易
11、见,当图中只要有一个奇点时,就不可能那样走一遍了,因为对一个路口来说,有走进去的一条路,必有走出来的一 条路.反之也不难证明,当道路图上没有没有奇点时,便可以那样走一遍了.如果起点和终点可以不同,则允许有两个奇点.这就是上节讨论的“一笔画”问题.回到邮路问题,如果道路图上没有奇点,问题就已经解决了.如果有奇点,我们总可以通过在某一些路上再重复走一遍的办法来消灭奇点,这相当于在图上再添一些路.在图中,是偶点,是奇点,因此,在图上要再添一些路来消灭奇点.如果在 和 之间,和 之间各添上一条路(即在2,3和5,6上走两次),奇点就没有了,于是就可以一笔画了.但我们还要求所走的路程最短,所以问题就归结
12、为:如何选择要重复的路程,使之既能消灭奇点,又能使重复的路程最短?14723562356这个问题已经被我国数学家管梅谷解决了,所以邮路问题又称为中国邮递员问题.他证明了只要在每个圈上所走的重复路 程不超过整个圈长的一半,就可以得到路程最短的走法.例如在上图中,如果重复 和 ,和 两条路,虽能消灭奇点,但在圈 上重复路程2+3=5已经超过整个圈长的一半(4.5),所以它不是路程最短的走法.我们可以改为重复 -,-,-,这样既消灭了奇点,又使得每个圈上的重复路程都不超过整个圈长的一半.于是就得到这样一个路程最短的走法:.综上所述,得出解决邮路问题的基本步骤如下:首先把道路图上所有的奇点都找出来,然
13、后选择一些需要重复的路,消灭奇点,再在每个圈上检查重复路程是否超过整个圈长之半,如有超过的情况,则在这个圈上,把原来不重复的路定为重复的路,而把原来重复的路定为不重复的路,这样逐步调整,当所有圈上的重复路程都不超过整个圈长之半时,就达到路程最短的要求了,最后将整个图形一笔画出.23562345622634451346575432621一般说来,一个图形所具有的圈数是很多的,是否每个圈都必须要检查?答案是否定的,如上图中共有6个圈,实际上 只要检查3个就够了.一般的,若一个图有s条路,n个顶点,则需要检查的圈数为s-n+1.这里提出的问题,不只是邮递员会碰到,在其他一些场合也会碰到,如在马路上扫
14、地、洒水的车子所走的路线.9.3 周游世界问题 人们在旅游时常常希望设计这样一条路线,能够不重复地经过所有想要游览的景点,而且路程最短.1859年,爱尔兰数学家哈密尔顿设计了一种叫做“周游世界”的游戏.游戏的玩具是一个正十二面体.如下图:哈密顿圈(环球旅行游戏)哈密顿圈(环球旅行游戏)在它的20个顶点上分别表有世界上20个著名的城市,每两个 顶点之间的棱表示这两个城市之间的可通行道路顶点之间的棱表示这两个城市之间的可通行道路.游戏的游戏的规则是:找出一条道路,使他从某个城市出发,经过所有规则是:找出一条道路,使他从某个城市出发,经过所有其他城市一次后返回原出发城市其他城市一次后返回原出发城市.
15、为方便起见,我们把这个十二面体投影到平面上保持原点、为方便起见,我们把这个十二面体投影到平面上保持原点、线之间的连接关系线之间的连接关系.能否在下图(能否在下图(2)中找出一条道路,使)中找出一条道路,使它从某个顶点出发,经过所有其他定点各一次后再回到出它从某个顶点出发,经过所有其他定点各一次后再回到出发点呢?发点呢?如果这条首尾相连的道路存在,我们把它叫做原图的一个如果这条首尾相连的道路存在,我们把它叫做原图的一个哈密尔顿圈,含有哈密尔顿圈的图称为哈密尔顿图哈密尔顿圈,含有哈密尔顿圈的图称为哈密尔顿图.我们注意到,哥尼斯堡七桥问题的几何模型与哈密尔顿周游我们注意到,哥尼斯堡七桥问题的几何模型
16、与哈密尔顿周游世界问题的几何模型有某些相似之处,即都是在图中寻找一世界问题的几何模型有某些相似之处,即都是在图中寻找一 条首尾相连的道路,都要求所走的路程最短条首尾相连的道路,都要求所走的路程最短.不同的是,前不同的是,前者所找的道路要经过所有的边恰好一次(每条边至少一遍)者所找的道路要经过所有的边恰好一次(每条边至少一遍),而后者则要求经过所有的顶点恰好一次(有的路可以不,而后者则要求经过所有的顶点恰好一次(有的路可以不走)走).解决哈密尔顿周游世界问题,可借助于解决哈密尔顿周游世界问题,可借助于“一笔画一笔画”的性质:的性质:如果图(如果图(2)中存在哈密尔顿圈,那么由于这个)中存在哈密尔
17、顿圈,那么由于这个“圈圈”是是一个一个“一笔画一笔画”图形,其所经过的点必都是图形,其所经过的点必都是“圈圈”上度数上度数为为2的偶点,在图(的偶点,在图(2)中,这个)中,这个“圈圈”要经过要经过20个顶点,个顶点,而所有顶点的度数之和为边数的两倍,由此可知而所有顶点的度数之和为边数的两倍,由此可知“圈圈”上上的边数为的边数为20.已知正十二面体共有已知正十二面体共有30条边,于是问题转化条边,于是问题转化为:能否抹去为:能否抹去10条边,使图中(条边,使图中(2)中)中20个顶点的度数都个顶点的度数都变为变为2.这是可以做到的这是可以做到的.第10章 数学建模的常见方法10.1 数据建模法
18、 在用数学模型解决实际问题时,如果能够利用物理、化邓自然科学的规律来建立数学模型,就把这种建模的方法称为机理分析法.但是在不少实际问题中,人们所掌握的仅仅是一些通过检测所得到的数据资料,根据这些数据建立尽量符合问题实际的数学模型,称为数据建模法.这里所说的数据资料是指人们从实际问题中收集得到的事实观察值和测量值.它是数学模型与实际问题相联系的重要途径和手段.由于来自实际的数据资料有可能是不精确的,或者是不完善的,因此建模过程中处理好数据资料和模型的关系非常重要的.在使用数据建模法时,有时所采集的数据资料对于建模与分析已经足够了,无需另外采集更多的数据;有时则不然,得从采集数据做起.收集有效数据
19、并不是一件容易的事,一般得注意以下两点(1)收集数据应有明确的目标.(2)对于收集得来的数据应作适当的预处理.在建模过程中,数据资料的作用很大,主要体现在以下三个方面:(a)在建模过程中(特别是在建模的初期),当我们开始构架问题的模型时,数据资料能够对我们所构架模型给予了提示.有些模型(如经验模型)则是完全建立在数据资料的基础之上.(b)数据资料可以帮助我们对模型的参数给出估计.使用数据资料给出模型参数值的估计过程,我们称之为模型的参数估计.(c)数据资料还可以用于检验模型的效果,也就是检验由模型计算出来的理论数据是否合理地反映了实际的观测结果.如果有若干个模型描述同一个实际问题时,模型效果的
20、检验可以帮助我们选择最优的模型.本节主要讨论数据建模的两种情形,即由确定性数据建模和由随机性数据建模.10.1.1 从不同角度看待数据资料 解决问题最重要的往往并不是怎样将数据代入公式,而是要确定哪些数据、哪些因素对事件有影响.请看下面的例子.例1.香港地区的中学数学教材中有这样一个题目:某企业有股东5人,工人100人,19901992年的3年间,该企业的收益情况如表所示,要求根据表中数据绘制一幅坐标图.年份股东利润(万元)工资总额(万元)1990年1991年1992年 5 7.5 10 10 12.5 15 面对这样一组数据,不同的思维哦方法可以构建出不同的数学模型,描绘出不同的图形.可以是
21、两条平行线,传递出的信息是劳资双方共同发展,有福同享、有难同当。这样的图形是老板最愿意看到的,我们姑且称它为“老板图”。也可以那全体股东利润增长的比例和全体工人工资增长的比例作比较,以1990年为起点(100),3年后,股东利润增长了100%,而工人工资只增长了50%.这幅图传递出来的信息是工人工资的增长比例是股东利润增长比例的一半,应该适当增加工人的工资,我们把它称为“工会图”.我们还可以那股东跟人收入的增长和工人个人收入的增长作比较,传递出来的信息则是股东和工人的收入差距十分悬殊,而且差距越来越大,这样的图可称为“工人图”.华东师大的张奠宙教授拿这一题目请一位教师到中学做实验,让同学们根据
22、数据汇出图来。结果100%的学生绘制出第一个图形.在学生们看来,第一个图是最规范的思路,也是最标准的答案,他们根本没想过这一题目会具有多种答案,也没有想过一组数据中透露出来的生活中的实际信息,而只是想到把这一题目解出来就行了.由此可见,面对不同的数据或条件、不同的需要、不同的构思,完全可能建立起不同的数学模型来,关键在于我们看待问题要多角度,思维力求发散.10.1.2 依据确定性数据的建模方法 在某种变化过程中,所涉及的变量之间存在某种确定性的函数关系,检测所得的数据资料仅仅是这种确定性的函数关系在量上的反映,我们把这种情况称为确定性现象.既然此时变量之间存在确定性的函数关系,那么就需要我们通
23、过对数据资料进行分析处理,来揭示其内在的函数关系,建立数学模型.一个简单的例子就是,圆的周长C与直径d之间的关系.不同的圆有不同的周长,人们通过大量的检测数据,揭示了这一本质关系,建立了函数模型 C=d 其中圆周率是一个常数3.141592653例10-2 跳板承受力的问题依据随机性数据的建模方法10.3 统筹法10.3.1 定义 一项工程由若干道工序组成,每道工序都需要一定的工期,各道工序之间存在一定的前后衔接关系,那么工程进度如何安排呢?解决这类问题的方法一般是统筹法,国外又叫做计划外评审方法.又称网络计划法。它是以网络图反映、表达计划安排,据以选择最优工作方案,组织协调和控制生产(项目)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 模型 笔画
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内