用数学建模方法解决哥尼斯堡七桥问题

1、标签:标题篇一：哥尼斯堡七桥问题教学实录“哥尼斯堡七桥问题”教学实录一、 创设情境，激趣引思1 .故事引入师：这节课，我们先来听一个数学小故事吧。（课件播放，如图1,教师相机板书课题）师：这个问题困扰了当地居民很长时 司，大家纷纷来到小岛上试图找到答案，但都无功而返。因为根据计算，每次都走完七座桥的所有走法共有5040种，这么多怎么走得完呢 ？后来有人写信向当时公认的“天才数学家”欧拉请教。欧拉亲自来到小岛上实地考察，也未找到答案。但他是一个不向困难低头的人，经过一年的研究，终于解决了这个问题。原来他将七桥问题题转化为一笔画问题，才顺利找到答案的。（教师板书：一笔画）2 .释疑。师：谁能根据你

2、的理解，来说一说什么是一笔画？（教师请一个学生上台画图说明 ）师：（利用课件动态演示）像长方形、正方形、三角形等都能够一笔画出。（并结合长方形介绍：两条线相交的点，叫做交点。如图2）交点师：哥尼斯堡七桥问题，大家可能觉得有点复杂。我们先从简单的图形人手，来探究一笔画中的学问。二、自主探究，合作交流交点（一）探究活动一。1.探究。 图2师：下面请二人小组合作，共同完成探究记录单，首先请看活动要求。（课件出示记录单和活动要求）活动要求：（1）试一试，在空白处画一画，判断图形能否一笔画出，并在相应的口里打。（2）对于能够一笔画出的图形，请沿不同交点出发，探索它有几种不同的画法。（学生探究，教师巡视指

3、导）3 .交流。师：很多小组都已经有答案了，谁来汇报一下你们探究的结果？生1: 1号图是不能一笔画出的，因为它们是分开的。师：谁听懂了他的意思？生2:他是说1号图中的三个“口”没有连通起来。师：是啊，像1号图这样，各个部分没有连通起来，就不可能一笔画出。这说明要能够一笔画出，它各个部分之间必须是连通的。画出。（板书：必须是连通图）接下来，谁继续汇报？生3: 2号图是可以一笔画出的。师：是吗？你能到黑板上画一下吗 ？（学生上台画图，教师提示他在起点处标上字母“ A”,如图3）图3师：很好！他刚才是从A点出发，一笔画出了这个平行四边形。 那么，只能从A点出发吗？生4:从其他交点出发也可以。（大家纷

4、纷赞同）师：你们都实验过吗？的确，这个平行四边形无论从哪个交点出发，都可以一笔画出来。那么3号图可以一笔画出来吗 ？生5:可以的。（教师请生5上台画图，教师给生 5画的图各交点标上字母，如图 4）师：真厉害，他的确是一笔画出的。我发现他是从E点出发画的。那么这幅图还能从其他交点出发画出来吗？B生6:我还可以从 F点出发，也可以一笔画出。F师：还有其他画法吗？生7:我还可以从 A点出发。（教师请生7上台画，生7尝试了多种路径，均未成功 ）师：（摸着生7的头）我很佩服他，虽然他最后没有成功，但是他这种执着探索的勇气还是可嘉的。从A点出发不可以，还有哪些点也会出现这样的状况呢？生8:我认为，从B、C

5、、D点出发也是不能一笔画成的，因为它们和A点所处的位置是相似的。师：很好，你真是善于观察！那你们有没有想过，虽然 2号图和3号图都能一笔画成，但是2号图可以从任意一点出发，而 3号图只能从E点和F点出发才可以一笔画出，这里面有没有什么奥秘呢？（学生陷入沉思。片刻之后，渐渐地有几只小手举起来）生9:因为那个“日"字形状的图形里面多了一横。师：（装糊涂）什么意思？你能具体解释一下吗 ？生9:就是说本来画那个“日”字周围边框的时候，是可以一笔成功的：但是中间多了那个一横，就必须从这一横出发才可以成功。师：你很有数学家的潜质！你的发现对我们接下来的研究意义重大。大数学家欧拉就是这样发现规律的

6、，连通图能否一笔画出。与图中各个交点的连线条数有关。（二）探究活动二：1.介绍。师：（出示课件，如图5）像下面的A点和B点，连线条数是1、3、5、7等奇数的点，叫作奇点；像下面的 C点和D点，连线条数是2、4、6、8等偶数的点，叫作偶点。D奇点偶点2.研究。师：大家回过头来观察 2号、3号图形，看看各点的情况。生：2号图形全部是偶点：师：欧拉发现，像三号图中全是偶点，不仅可以一笔画，而且沿着任意一点都可以画出。这里的“任意”是什么意思 ？生：就是随便从哪个点出发都可以。师：是的，例如我们很多人都会画的五角星图案（课件出示图6）,它的各交点也都是偶点，所以也可以从任意一点出发一笔画出：你们不妨试

7、一试。（学生尝试）师：那3号图形呢？生：它有两个交点的连线条数是3,其余各交点都是偶点。师：3号图形中只有两个奇点，其他都是偶点，欧拉发现这样的图形虽然能够一笔画出，但是一一生：必须，从奇点出发。师：你和欧拉真是心有灵犀！的确必须从奇点出发。那么大家看，这个图形能不能一笔画出呢？（课件出示图7）生：它也可以一笔画出，但是必须从那两个奇点出发才行。师：你们都能学以致用了，真好 ！（三）思维训练，学以致用。师：下面我们来轻松一下，玩一次智慧大闯关好不好？1.夺宝小奇兵：藏宝庄园里有10个百宝箱（如图8）,每次可以打开宝盒取宝 1个。但是不能走重复路线， 否则就会触动机关取宝失败。现在蚂蚁宝宝和贝贝

8、站在不同的起点准备出发了，你认为谁能全部取宝成功？为什么？2、小设计师。（如图9）小朋友，妙妙游乐园即将开放了。要让游客一次不重复地沿着路线走，游完每一个游乐项目，游乐场的出口和入口应该设在A、B、C哪两个点上？3.生活中的应用。以游乐园出口和入口的设置以及快递叔叔送快件的例子，说明一笔画能够解决生活中的实 际问题。（四）探究活动三。师：那么，是不是所有的连通图都能一笔画呢？我们继续探究。请大家看这幅图（课件出示图10）,数一数，标出它的奇点和偶点，并判断它能否一笔画出。生：我试了好多次，它不能一笔画出。师：其他同学有没有不同的看法？生：我也试了很多次，不能一笔画出。我猜想可能和它的奇点多了有

9、关系。师：你很善于推理，欧拉花了一年多时间发现的秘密，你们居然图10很快能领悟。欧拉发现，连通图中，如果奇点超过了 2个，它就不能一笔画出了。三、文化渗透，深刻理解师：现在我们回到之前的“哥尼斯堡七桥问题”,它跟一笔画知识有什么关系呢？让我们来了解一下。（教师利用课件动态演示由“七桥图”变成“抽象图”的过程，如图11）师：欧拉认为：能否一次不重复地走过这七座桥，与桥的长短、岛的大小无关，所以岛和 岸都可以看作一个点，而桥可以看作连接这些点的线。所以他将七桥问题抽象成这样的一笔 画图形。现在你能用今天学到的知识来解释为什么不能不重复地一次走遍这七座桥吗？生：因为把它变成这样的图形后，这个连通图中

10、有4个奇点，就不可能一笔画出了。师：是啊，就在“山重水复疑无路”的时候，欧拉是怎样实现“柳暗花明又一村”的？生：他将复杂的问题简单化了。师：的确，欧拉是将这个问题转化成了一笔画问题。（板书：转化）转化是我们学习数学的一个好方法。（利用课件介绍欧拉生平，如图12）师：想想看，欧拉能够发现这一重要规律，是因为他很幸运吗？还是有别的原因？生：我认为他很执着，坚持不懈，并用科学的方法找到结果。师：是啊，这里面有他对真理的执着追求，更有化难为易的“转化”思想。师：今天我们只是初步了解了一笔画知识，以后我们升人七年级还将继续深篇二：关于哥尼斯堡七桥问题的综述关于哥尼斯堡七桥问题的综述学生姓名：赵锋学生学号

11、：090741132联系方式要：随着科学技术的不断发展，图论的理论和方法已经渗透到物理、化学、通讯科学、 运筹学、遗传学、管理学、经济学、社会学等各门学科中，而且延伸出了超图理论、代数图 论、随机图论、网络图论等分支，大大丰富了图论学科内容，促进了图论研究和应用。由于 计算机科学技术的飞速发展和网络技术的广泛应用，图论作为计算机网络科学研究的基本工具和理论基础，会越来越受到人们的重视，不断推动图论学科继续向前蓬勃发展。本文通过阅读大量文献，总结出了图论的来源、应用及其未来的发展趋势。关键词：哥尼斯堡七桥、图论、一笔画关于哥尼斯堡七桥问题的综述引言经典问题往往以深入浅出

12、的形式表达学科深奥的科学规律和本质内容，在学科研究中常常 用来辅助说明思想、原理、方法和技术。出生于瑞士的伟大数学家欧拉( Leonhard Euler, 17071783)于1736年发表了论文 与位置几何有关的一个问题的解，文中提出并解决了七桥问题，为图论的形成奠定了基础。今天，图论已广泛应用在计算机学科、运筹学、控制 论、信息论等学科中，成为对现实世界进行抽象的一个强有力的数学工具。一、哥尼斯堡七桥问题的由来哥尼斯堡就是现在的俄罗斯的加里宁格勒。哥尼斯堡在第二次世界大战前属于德国，是东 普鲁士的首府，在历史上，哥尼斯堡的归属曾发生过几次变化。二战结束后，根据雅尔塔和 波斯坦协议，东普鲁士

13、部分领土划归苏联，是苏联作为战胜国享受的战利品。苏联把哥尼斯堡更名为加里宁格勒， 斯大林没有把加里宁格勒划入刚刚并如苏联的立陶宛，而是划入俄罗斯联邦。加里宁格勒风景秀丽，气候宜人这里有着丰富的自然资源，是重要的军事基地，也是重要的海运港口。 1991年苏联解体，波罗的海周边三国的立陶宛，拉脱维亚和爱沙尼亚 独立，加里宁格勒就变成了俄罗斯的一块飞地。普莱格尔河穿过美丽的哥尼斯堡城。普莱格尔河有两个支流，在城市中心汇成大河，中间 是岛区，人们在河上建起了七座桥，使这里成为风景优美的人间仙境，如图1所示。由于岛上有古老的哥尼斯堡大学，有知名的教堂，有大哲学家康德的墓地和塑像，因此城中的居民，尤其是大

14、学生们经常到河岸和上桥散步。在十八世纪初，有一天，有人突发奇想：如何才能走过七座桥， 而每座桥都只能经过一次， 最后又回到原来的出发点？当地的人们开 始沉迷于这个问题，在桥上来来回回不知走了多少次，然而却始终不得其解，这就是著名的哥尼斯堡七桥问题的由来。二、相应理论的开创一一图论通过数学建模，已经把实际问题转化成了数学问题。这时欧拉注意到，如果一个图形能一笔画成那么除去起点和终点外，其他的点都是经过点。而经过点是有进有出的点，即有一条线进这个点，就一定有一条线出这个点，不可能有进无出，如果有进无出，它就是终点；也 不可能有出无进，如果有出无进它就是起点。因此，在经过点进出的线总数应该是偶数。我

15、们称在一个点进出线的总数是偶数的点为偶点；总数为奇数的点称为奇点。如果起点和终点是同一个点，那么它也属于有进有出的点， 它也是偶点这样图上的点全是偶点。 如果起点 和终点不是同一个点， 那么它们必定是奇点。 因此，能够一笔画的图形最多只有两个奇点年 欧拉证明了自己的猜想，一次不重复。1936年，欧拉证明了自己的猜想，一次不重复走完七座桥是根本不可能的。随即他发表了 “一笔画定理”：一个图形要能一笔画完，必须符合以下两个条件：（1）图形是封闭连通的；（2）图形中的奇点个数为 0或1;七桥问题中的四个点全是奇点（如图2）,当然不能一笔画，即不可能一次无重复地走完七座桥。一般地说如果图中的点全是偶点

16、，那么可以任意选择一个点作为起点，当然终点与起点重合能一笔画成，如果图中有两个奇点， 那么可以任意选一个奇点作为起点，另一个奇点为终点可以一笔画成。欧拉的这个研究成果，开创了图论这门新的学科，这门学科在计算机科学中有着广泛的应 用。三、图论的应用1、一个部门中有 25人，由于纠纷而使得关系十分紧张，是否可便每个人与5个人相处融洽？这看起来是社会学领域的间题，我们可以尝试多种方法， 而其中的一种方法就是将其化为图。建立一个图的模型， 最基本的问题是如何描述它一什么是结点，什么是边？在本问题中，没有太多的选择，只有人和纠纷。我们可试着用结点来代表人。用边来代表图中结点之 间的关系，这是很常见的。在

17、这里结点之间的关系是“关系是否融洽”，因此，若两个结点（人）关系融洽，那么就在它们之间加上一条边。现在假设每个人与其他 5个人关系融洽。例如，在图一上显示出我们所描述的图的一部分， 小张与小王、小李、小赵、小黄和小吴关系融洽，再没有其他人。个人均是这种情况。这是 否可能在图论中，一个重要的推论在任意图中，具有奇数度的结点个数必为偶数。现在出现了矛盾：有25 （奇数）个具有5 （奇数）度的结点。因此，该间题是不可能实现的。2、举行一个国际会议，有 a, b, c, d, e, f, g等7个人。已知下列事实： a会讲英语；b会讲英语和汉语；c会讲英语、意大利语和俄语；d会讲日语和汉语；e会讲德语

18、和意大利语；f会讲法语、日语和俄语；g会讲法语和德语。试问这7个人应如何排座位，才能使每个人都能和他身边的人交谈？这个问题看起来很熟悉。我们还是用图解这个问题。依然是建立一个图的模型，确定结点和边。这里有“人和语言 ”，那么我们用结点来代表人，于是结点集合 V=a、b、c、d、e、 f、g。对于任意的两点，若有共同语言，就在它们之间连一条无向边， 可得边集 巳图G=（V , E）,如图二：如何排座位使每个人都能和他身边的人交谈？问题转化为在图G中找到一条哈密顿回路的问题（哈密顿回路即是通过每个结点一次且仅一次的回路。而即是图中的一条哈密顿回路）。照此顺序排座位即可。3、有三座城市C1、C2、C

19、3以，要修建高速公路与另外三座城市 C4, C5, C6直接相连通。 能否设计一个公路网使任意两个高速公路之间彼此不交叉？这是一个涉及交通方面的问题。很显然我们用结点代表城市，两城市之间修建高速公路， 则在它们之间连一条无向边。图三所示是一个存在交叉的设计方案。当你试着找出一个不存在交叉的设计方案时，很快就会发现不可能做到这一点。我们给出一个定义：如果一个图能够在平面中画出来，且任意两条边不相交，则该图就是 平面图。在设计电路时要求相交的线尽可能的少，因此，电路设计者面临的主要问题就是平面性问 题。当在一个平面上画出一个连通的平面图时，该平面被分成几个连续的区域，这样的区域被 称为面，我们称图

20、G=(V, E),点集V的个数为v,边集E的个数为e,若G是平面图，面的个 数为fo早在1752年，欧拉证明了对于任何连通的平面图均满足等式：f=e-v+2。图三被我们称作k3.3,现在我们用来证明 k3.3不是平面图。假设k3.3是平面图，面数为f,因为每一条回路最少有四条边，所以每个面的边界至少有 四条边围成，所有边界所含的边的总数至少等于4f。在平面图中，每一条边最多属于两个面的边界回路，所以有所以，在这里无法设计一个公路网，使任意两个高速公路彼此不交叉。四、总结从诸多具体实例可以看出，图论之所以得到迅猛发展在于它独特的解题思想：将繁琐的问 题抽象成图论模型，通过直观的图形来论证。 也正

21、因此，图论的理论和方法已经渗透到物理、 化学、通讯科学、运筹学、遗传学、管理学、经济学、社会学等学科中，进而延伸出了超图 理论、代数图论、随机图论、网络图论等分支，大大丰富了图论学科内容，促进了图论研究 和应用。目前，由于计算机科学技术的飞速发展和网络技术的广泛应用，图论作为计算 篇三：从哥尼斯堡七桥问题看数学抽象性从哥尼斯堡七桥问题看数学的抽象摘要：由哥尼斯堡七桥问题出发，分析其蕴含的思想、方法，并引出数学抽象方法的概念，定义，特点及运用.关键字：七桥问题；抽象；特点；方法数学无论是在内容上还是方法上都呈现出极其高度的抽象性.数学的抽象有两个基本特征 ：概括性和深刻性.用数学方法思考事物时，

22、往往把这些事物的物理属性、化学属性和生物属 性等全撇开，而只考虑其量的特征、形的特征.以下以哥尼斯堡七桥问题为例谈数学的抽象.一、哥尼斯堡七桥问题简介哥尼斯堡七桥问题是欧拉用抽象的方法探究并解决实际问题的一个典型实例，对开创图论 与拓扑学的研究具有重大意义 .18世纪的哥尼斯堡是德国的一个美丽的城市(现属于俄罗斯)，布勒尔河穿城而过，它有两个支流，在哥尼斯堡城中心汇成大河，河中心有一个小岛，河上有七座桥，如图1(1)岛上有一座古老的大学，还有哲学家康德的墓地及塑像.当地的居民，特别是大学生们常常到七桥附近散步，渐渐地大家热衷于一个问题：一个人是否能不重复地一次走遍这七座桥而返回出发点？很多人做

23、过尝试，但都未能实现，这便产生了数学史上著名的“七桥问题”，1735年，一群大学生写信将这个难题交给了著名的数学家欧拉.图1欧拉首先从千百人次的失败中猜想，也许根本不可能不重复地一次走遍这七座桥，但如何 来证明它呢？欧拉是这样想这个问题的：既然岛与两岸无非是桥的连接地点，两岸陆地也是桥通往的地点，那么就不妨把这四处地 点抽象成四个点，并把七座桥抽象成七条线，这样在不改变问题的实质的前提下，问题就转化成了一个有关几何图形的问题，如图1(2)所示，即人们步行走过两岸和七座桥时，就相当于用笔画出此图.于是问题转化为：能否用笔不重复地一笔画出此图.接着欧拉进一步研究了一笔画问题的结构和特征：一笔画有一

24、个起点和一个终点，当起点和终点重合时， 称该图形为封闭图形，否则称为开放图形 .除起点和终点外，一笔画中间可能出现一些曲线的交点， 在这些交点处曲线一进一出，因此其连结的曲线总是偶数条，这些交点就称为“偶点”，由此看来，只有起点和终点通过的曲线可能是奇 数条，称通过曲线是奇数条的起点和终点为“奇点”，特别地，当起点和终点重合时，便成为一个偶点，不再是奇点.正是通过上述研究， 欧拉断言：任何一个一笔画， 要么没有“奇点”，要么恰有两个“奇点”， 而在“七桥问题”所对应的图形中，四个点都是“奇点”，因此它不能一笔画成，从而说明人们不可能不重复地一次走过哥尼斯堡的七座桥欧拉没有满足于“七桥问题”的解

25、决，而是继续深入研究，终于用严密的数学语言证明了 一个可鉴别任一图形能否一笔画出的“一笔画定理”：一个网络（任意一个有限条弧线构成的图形，且每条弧线都有两个相异的端点）是一笔画，当且仅当该网络是连通的，并且奇顶点的个数是0或2.欧拉解决这一问题所用的思维方法，就是抽象方法，即从感性认识上升到理性抽象，再由 理性抽象升华为理性认识，这也是人们认识事物常用的一种抽象思维方式.“七桥问题”有力地说明，数学抽象将实际问题中许多无关紧要的东西（如桥的大小、形状之类）舍去，而紧紧抓住其中带有本质特征的东西，从而构造出一些在逻辑上无矛盾的“纯粹”的数学关系.二、数学抽象的概念数学是反映现实世界的，它产生于人

26、类的实际需要.数学最初概念与原理的建立，是以经验为基础的长期历史发展的结果 .对于现实世界的一个特定对象，一个特定目的，想要研究其存在的规律，这需要人们对现 实问题进行深入细微的观察和分析，又需要人们灵活巧妙地利用各种数学知识.比如实际问题中有许多因素，在建立数学模型时，不可能，也没有必要把它们毫无遗漏地全部加以考虑， 只需考虑其中的最主要的因素即可.根据其特有的内在规律，做出一些必要的假设，运用适当的数学工具，通过抽象、简化、引进变量等处理过程，将实际问题用数学方式表达，即用 数学式子（如函数，图形，代数方程，微分方程，积分方程等）来描述（表达，模拟）所研 究的客观对象或系统在某一方面的规律

27、，然后运用数学方法及计算机技术进行求解数学抽象是抽象方法在数学中的具体运用，也就是利用抽象方法把大量生动的关于现实世 界空间形式和数量关系的直观背景材料进行去伪存真，由此及彼，由表及里的加工和制作， 即提炼数学概念，构造数学模型，建立数学理论 三、数学抽象的特点抽象性在简单的数字运用中就得以体现，比如两个抽象数字相乘，我们关心的并不是孩子 的数目乘以苹果的数目， 还是苹果的数目乘以苹果的单价.直线、 平面、空间都是抽象的概 念，n维空间乃至无穷维空间也都是抽象的概念.数学抽象的特点在于以下几个方面：第一，在数学的抽象中只保留量的关系和空间形式而舍弃了其他一切，这里量是抽象的，空间也是抽象的，如

28、圆的方程，数域F上的线性空间等概念，只剩下了变量之间的关系和运算.第二，数学的抽象是一级一级逐步提高的，它们所达到的抽象程度大大超过了其它学科中的抽象，首先，数学抽象往往是在其他学科抽象基础上的再抽象.例如，正比例函数是物理学中匀速直线运动和简谐运动的再抽象.其次，数学抽象具有逐级抽象的特点.更为重要的是，数学抽象的特殊性表现在数学中一些概念与真实世界的距离是如此遥远以致常常被看成“思维的自由想象物和创造物”，即数学中所谓的“理想元素”（如无穷远点）.比如说，我们生活的这个现实世界是个三维空间，人们对于一维、二维及三维空间很熟悉， 在这三种空间中任何两点问的距离可以度量出来，很直观，四维以上的

29、空间，我们就看不见模不着了，至于无限维空间是什么样就很难理解.第三，数学本身几乎全在处理抽象才念和它们的相互关系.自然科学家为了证明自己的论断常常求助于实验，而数学家证明定理只需用推理和计算总之，量和空间是抽象的，概念是抽象的，数学的方法也是抽象的.四、数学抽象的基本方法1 .理想化抽象在纯粹理想的状态下，对事物进行简单化与完善化的加工处理，撇开事物的具体内容，排除次要的、偶然的因素，融合事物的一般的本质的属性，抽象出相应数学内容的方法.例如:经济学上的多年度经济预测，年降雨量的年度曲线绘制2 .强抽象与弱抽象强抽象是指在已知概念中，加强对某一属性的限制，抽象出作为原概念特例的新概念的方法，即

30、通过扩大原概念的内涵缩小外延来建立新概念的抽象方法例如:从四边形概念出发， 对两组对边给予适当限制，则得平行四边形和梯形的概念 .若从平行四边形概念出发，再对边或角分别进行适当限制，可得到菱形、矩形及正方形的概念.弱抽象是指在已知概念中，减弱对某一属性的限制，抽象出比原概念更为广泛的新概念，使原概念成为新概念的特例的方法，即通过缩小原概念的内涵扩大外延来建立新概念的抽象方法.例如:从全等三角形概念出发，借助弱抽象就可获得相似形与等积形的概念，它们分别保留 了 “形状相同”与“面积相等”的特性 .3 .等置抽象从一类对象（具体的或抽象的个体）中抽象出其中的某种共同属性的抽象方法例如：实数集上的全

31、体n阶方阵，考虑的运算为矩阵的加法； 实数集上的行列式为 1的全体n 阶方阵，考虑的运算为矩阵的乘法；模 n的剩余类，其运算为规定的剩余类间的加法等等 . 这些集合既有有限集合，也有无限集合，运算也各不相同，但却具有相同的属性，即：关于运算封闭，结合律成立，每个集合都有单位元，每个元素有逆元，从而抽象出群的概念.4 .存在性抽象先用假设的方法对抽象出来的数学概念存在给予肯定，并由此发展出一定的数学理论，然后在理论和实践中加以验证，从而确认新的数学理论的合理性例如：自然数集合？n?是经过三个层次抽象而成的，被称为三度抽象物：古代人们在生产实践中，用“结绳计数”的方法，由计算个别具体数量而得到个别自然数的概念.这是第一步抽象.第二步，人们从数个别自然数中发现进行“加一”的运算，可以得到后继数，