哥尼斯堡七桥问题

七桥问题Seven Bridges Problem著名古典数学问题之一。

在哥尼斯堡的一个公园里，有七座桥将普雷格尔河中两个岛及岛与河岸连接起来(如图)。

问是否可能从这四块陆地中任一块出发，恰好通过每座桥一次，再回到起点?欧勒于1736年研究并解决了此问题，他把问题归结为如下右图的“一笔画”问题，证明上述走法是不可能的。

有关图论研究的热点问题。

18世纪初普鲁士的柯尼斯堡，普雷格尔河流经此镇，奈发夫岛位于河中，共有7座桥横跨河上，把全镇连接起来。

当地居民热衷于一个难题：是否存在一条路线，可不重复地走遍七座桥。

这就是柯尼斯堡七桥问题。

L.欧拉用点表示岛和陆地，两点之间的连线表示连接它们的桥，将河流、小岛和桥简化为一个网络，把七桥问题化成判断连通网络能否一笔画的问题。

他不仅解决了此问题，且给出了连通网络可一笔画的充要条件是它们是连通的，且奇顶点(通过此点弧的条数是奇数)的个数为0或2。

当Euler在1736年访问Konigsberg, Prussia(now Kaliningrad Russia)时，他发现当地的市民正从事一项非常有趣的消遣活动。

Konigsberg城中有一条名叫Pregel的河流横经其中，这项有趣的消遣活动是在星期六作一次走过所有七座桥的散步，每座桥只能经过一次而且起点与终点必须是同一地点。

Euler把每一块陆地考虑成一个点，连接两块陆地的桥以线表示。

后来推论出此种走法是不可能的。

他的论点是这样的，除了起点以外，每一次当一个人由一座桥进入一块陆地（或点）时，他（或她）同时也由另一座桥离开此点。

所以每行经一点时，计算两座桥（或线），从起点离开的线与最后回到始点的线亦计算两座桥，因此每一个陆地与其他陆地连接的桥数必为偶数。

七桥所成之图形中，没有一点含有偶数条数，因此上述的任务无法完成.欧拉的这个考虑非常重要，也非常巧妙，它正表明了数学家处理实际问题的独特之处——把一个实际问题抽象成合适的“数学模型”。

1736年29《哥尼斯堡的七座桥》的论文，创了数学的一个新的分支—一、哥尼斯堡七桥问题哥尼斯堡在俄罗斯境内，现称为加里宁格勒.生和培养过许多伟大人物.格尔河，横贯城中，如图1所示.流，一条称为新河，一条主流，的商业中心.区、北区、东区和南区.桥，两支流上.这一别致的桥群，图1早在18世纪，散步中走过每座桥，发点？”走遍这七座桥共有A77=7!=验，谈何容易.那么在这5040而形成了著名的图2欧拉请他帮助解决这个他似乎看到其中.经过一年的研究，29岁的并于1736年向彼得堡科哥尼斯堡的七座桥》的论文.C（岛区）、A（南区）；七座桥看成这四个点、6、7七个数字表示，如图3所示.“一笔画”问题：否能一笔不.布勒格尔河模型蔡思明58遍历的路径称作欧拉路径（一个环或者一条链），如果路径闭合（一个圈），则称为欧拉回路.图论中的欧拉定理（一笔画定理）要分有向图（边有特定方向的图）与无向图（边没有特定方向的图）两种情况进行讨论.1.无向图的情况定理：连通无向图G有欧拉路径的充要条件为：G中奇度顶点（即与其相连的边数目为奇数的顶点）有0个或者2个.证明：必要性.如果图能够被一笔画成，那么对每个顶点，考虑路径中“进入”它的边数与“离开”它的边数（注意前提是无向图，所以我们不能称其为“入边”和“出边”）.很显然这两个值要么相同（说明该顶点度数为偶），要么相差1（说明该顶点度数为奇）.也就是说，如果欧拉路径不是回路，奇度顶点就有2个，即路径的起点和终点；如果是欧拉回路，起点与终点重合，则不存在奇度顶点.必要性得证.证明：充分性.如果图中没有奇度顶点，那么在G中随机取一个顶点v0出发，尝试构造一条回路c0.如果c0就是原路，则结束；如果不是，那么由于图是连通的，c0和图的剩余部分必然存在某公共顶点v1，从v2出发重复尝试构造回路，最终可将整张图分割为多个回路.由于两条相连的回路可以视为一条回路，所以该图必存在欧拉回路.如果图中有2个奇度顶点u和v，那么若是加一条边将u和v连接起来的话，就得到一个没有奇度顶点的连通图，由上文可知该图必存在欧拉回路，去掉这条新加的边，就是一条以u和v为起终点的欧拉路径.充分性得证.可知，哥尼斯堡七桥问题中的图有4个奇度顶点（1个度数为5，3个度数为3），所以不存在欧拉路径.2.有向图的情况定理：底图连通的有向图G有欧拉路径的充要条件为：G的所有顶点入度和出度都相等；或者只有两个顶点的入度和出度不相等，且其中一个顶点的出度与入度之差为1，另一个顶点的入度与出度之差为1.显然，可以通过与无向图情况相似的思路来证明，过程略.当时的数学界起初并未对欧拉解决七桥问题的意义有足够的认识，甚至有些人仅仅当其为一个数学游戏.图论这一数学分支诞生后并未得到很好的发展，直到200年后的1936年，匈牙利数学家科尼希出版了《有限图与无限图理论》，此为图论的第一部专著，其总结了进200年来有关图论的成果，这是图论发展的第一座里程碑.此后，图论进入发展与突破的阶段，又经过了半个多世纪的发展，现已成为数学科学的一个独立的重要分支.图论原是组合数学中的一个重要课题.我们用点表示事物，用连接点的边表示事物间的联系，便可得到图论中的图.图论为研究任何一类离散事物的关系结构提供了一种框架.图论中的理论已应用于经济学、心理学、社会学、遗传学、运筹学、逻辑学、语言学计算机科学等诸多领域.由于现代科学尤其是大型计算机的迅猛发展，使得图论大有用武之地，无论是数学、物理、化学、地理、生物等基础科学，还是信息、交通、战争、经济乃至社会科学的众多问题，都可以运用图论方法予以解决.当然，图论也是计算机科学的基础学科之一.值得一提的是，欧拉对七桥问题的研究，后演变成多面体理论，得到了著名的欧拉公式V+F=E+2，欧拉公式是拓扑学的第一个定理.哥尼斯堡的七座桥如今只剩下三座，一条新的跨河大桥已经建成，它完全跨过河心岛——内福夫岛，导游们仍向游客讲述哥尼斯堡桥的故事，有的导游甚至仍称“七桥问题”没有被解决，留给游客以遐想.虽然七座哥尼斯堡桥成了历史，但是“七桥问题”留下的“遗产”不像这些桥那样容易破坏，欧拉卓越的解答方式被永载史册.60。

哥尼斯堡七桥问题[欧拉图]⼀、历史背景1736年，年仅29岁的数学家欧拉来到普鲁⼠的古城哥尼斯堡（哲学家康德的故乡，今俄罗斯加⾥宁格勒）。

普瑞格尔河正好从市中⼼流过，河中⼼有两座⼩岛，岛和两岸之间建筑有七座古桥。

欧拉发现当地居民有⼀项消遣活动，就是试图每座桥恰好⾛过⼀遍并回到原出发点，但从来没⼈成功过。

欧拉证明了这种⾛法是不可能的。

现在看来，欧拉的证明过程⾮常简单，但他对七桥问题的抽象和论证思想，开创了⼀个新的学科：图论(Graph)。

如今，⽆论是数学、物理、化学、天⽂、地理、⽣物等基础科学，还是信息、交通、经济乃⾄社会科学的众多问题，都可以应⽤图论⽅法予以解决。

图论还是计算机科学的数据结构和算法中最重要的框架（没有之⼀）。

⾸先能想到的证明⽅法是把⾛七座桥的⾛法都列出来，⼀个⼀个的试验，但七座桥的所有⾛法共⽤7\！=5040种，逐⼀试验将是很⼤的⼯作量。

欧拉作为数学家，当然没那样想。

欧拉把两座岛和河两岸抽象成顶点，每⼀座桥抽象成连接顶点的⼀条边，那么哥尼斯堡的七座桥就抽象成下⾯的图：Processing math: 100%假设每座桥都恰好⾛过⼀次，那么对于A、B、C、D四个顶点中的每⼀个顶点，需要从某条边进⼊，同时从另⼀条边离开。

进⼊和离开顶点的次数是相同的，即每个顶点有多少条进⼊的边，就有多少条出去的边，也就是说，每个顶点相连的边是成对出现的，即每个顶点的相连边的数量必须是偶数。

⽽上图中A、C、D四个顶点的相连边都是3，顶点B的相连边为5，都为奇数。

因此，这个图⽆法从⼀个顶点出发，遍历每条边各⼀次。

欧拉的证明与其说是数学证明，还不如看作是⼀个逻辑证明。

⼀个曾难住那么多⼈的问题，竟然是这样⼀个简单的出⼈意料的推理，还开创了⼀个新的学科。

欧拉⾮常巧妙的把⼀个实际问题抽象成⼀个合适的数学模型，这种研究⽅法就是我们应该掌握的数学模型⽅法。

这并不需要运⽤多么深奥的理论，但能想到这⼀点，却是解决问题的关键。

哥尼斯堡七桥问题与图论
大家公认，图论诞生于七桥问题。

出生于瑞士的伟大数学家欧拉（Leonhard Euler，1707—1783）于1736年发表了论文《与位置几何有关的一个问题的解》，文中提出并解决了七桥问题，为图论的形成奠定了基础。

今天，图论已广泛应用在计算机学科、运筹学、控制论、信息论等学科中，成为对现实世界进行抽象的一个强有力的数学工具。

七桥问题是这样描述的：17世纪的东普鲁士有一座哥尼斯堡城（现在叫加里宁格勒，在波罗的海南岸），城中有一座岛，普雷格尔河的两条支流环绕其旁，并将整个城市分成北区、东区、南区和岛区4个区域，全城共有七座桥将4个城区连接起来，图1是这条河以及河上的两个岛和七座桥的草图。

于是，产生了一个有趣的数学难题：一个人是否能在一次步行中穿越全部的七座桥后回到起点，且每座桥只经过一次？
为了解决哥尼斯堡七桥问题，欧拉用A、B、C、D表示4个城区，用7条线表示7座桥，将哥尼斯堡七桥问题抽象为一个图模型，如图2所示，从而将哥尼斯堡七桥问题抽象为一个数学问题：求经过图中每条边一次且仅一次的回路，后来人们称之为欧拉回路。

欧拉论证了这样的回路是不存在的，并且将问题进行了一般化处理，即对于任意多的城区和任意多的桥，给出了是否存在欧拉回路的判定规则：
（1）如果通奇数桥的地方多于两个，则不存在欧拉回路；
（2）如果只有两个地方通奇数桥，可以从这两个地方之一出发，找到欧拉回路；
（3）如果没有一个地方通奇数桥，则无论从哪里出发，都能找到欧拉回路。

哥尼斯堡七桥问题给我们的启示
哥尼斯堡七桥问题是欧洲数学家欧拉在18世纪提出的一个著名的数学问题，这个问题是如何通过哥尼斯堡城市中的七座桥，每座桥只能过一次，将城市中的四块陆地分隔开来。

这个问题最终被欧拉用图论的方法解决了，也成为了现代数学和计算机科学的基础之一。

哥尼斯堡七桥问题给我们的启示是：
创新思维：欧拉在解决这个问题时，采用了新颖的图论方法，这种创新的思维方式对于解决其他问题也同样适用。

抽象思维：欧拉将哥尼斯堡城市的地图抽象成为图形，通过对图形的分析和计算，解决了这个问题。

这种抽象思维方式，对于解决其他问题也同样重要。

多角度思考：欧拉在解决这个问题时，考虑了不同的角度和方法，最终找到了解决问题的突破口。

在日常生活和工作中，也需要多角度思考问题，寻找解决问题的最佳方法。

团队协作：欧拉在研究这个问题时，与其他数学家和科学家进行了交流和合作，共同解决了这个问题。

在工作中也需要团队协作，共同解决问题，取得更好的成果。

总之，哥尼斯堡七桥问题是一个启示我们创新思维、抽象思维、多角度思考和团队协作的经典案例。

18世纪著名古典数学问题之一。

在哥尼斯堡的一个公园里，有七座桥将普雷格尔河中两个岛及岛与河岸连接起来(如图)。

问是否可能从这四块陆地中任一块出发，恰好通过每座桥一次，再回到起点？欧拉于1736年研究并解决了此问题，他把问题归结为如下右图的“一笔画”问题，证明上述走法是不可能的。

18世纪德国哥德堡有一条河，河中有两个岛，两岸于两岛间架有七座桥。

问题是：一个人怎样走才可以不重复的走遍七座桥而回到原地。

这个问题好像与数学关系不大，它是几何问题，但不是关于长度、角度的欧氏几何。

很多人都失败了，欧拉以敏锐的数学家眼光，猜想这个问题可能无解（这是合情推理）。

然后他以高度的抽象能力，把问题变成了一个“一笔画”问题，能否从一个点出发不离开纸面地画出所有的连线，使笔仍回到原来出发的地方。

以下开始演绎分析，一笔画的要求使得图形有这样的特征：除起点与终点外，一笔画问题中线路的交岔点处，有一条线进就一定有一条线出，故在交岔点处汇合的曲线必为偶数条。

七桥问题中，有四个交叉点处都交汇了奇数条曲线，故此问题不可解。

欧拉还进一步证明了：一个连通的无向图，具有通过这个图中的每一条边一次且仅一次的路，当且仅当它的奇数次顶点的个数为0或为2。

这是他为数学的一个新分枝――图论所作的奠基性工作，后人称此为欧拉定理。

第二节哥尼斯堡七桥问题教学目标1.了解哥尼斯堡七桥问题的由来2.理解欧拉解决哥尼斯堡七桥问题的方法3.掌握一笔画问题的步骤教学重点掌握一笔画问题的技巧教学过程一、导入哥尼斯堡七桥问题的由来哥尼斯堡曾是东普鲁士的首府，现称加里宁格勒，在俄罗斯境内。

在第二次是世界大战时，的军警哲理入侵波兰。

后来，苏军也是从此地打进德国的。

所以哥尼斯堡是一座历史名城。

同时，在这里诞生和培养过许多伟大人物。

如著名唯心主义哲学家康德，终生没有离开此城。

在哥尼斯堡城中有一条布勒格尔河，横贯城中。

河有两条支流，一条称新河，一条叫旧河，在城中心汇合成一条主流，在合流的地方中间有一座河心岛，这是城中繁华的商业中心。

由于布勒格尔河的流过，使全城分成为四个地区：岛区、北区、东区和南区。

在布勒格尔河上，架了七座桥，其中五座将河岛与河岸连接起来，另有两座架在二支流上。

这一别致的桥群，吸引了众多的哥尼斯堡居民和游人来此河边散步或去岛上买东西。

早在18世纪，就有人提出这样的问题：“能否在一次散步中每座桥都走一次，而且只能走一次，最后又回到原来的出发点？”这个问题吸引了不少人去思考实验。

事实上，要走遍这七座桥的所有走法共有7！=5040种，要想一一验过，谈何容易。

是否在这5040中走法中存在着一条走遍七座桥而又不重复的路线呢？谁也回答不了。

因而形成了著名的“哥尼斯堡七桥问题”。

二、新授哥尼斯堡七桥问题的解决1735年，有几名大学生写信给当时正在俄国彼得堡科学院任职的天才数学家欧拉，请他帮忙解决。

欧拉并未轻视生活小题，他似乎看到其中隐藏着某种新的数学方法。

经过一年的研究，29岁的欧拉于1736年向彼得堡科学院递交了一份题为《哥尼斯堡的七座桥》的论文，圆满地解决了这一问题，同时开创了数学的一个新分支——图论。

问题的抽象——数学化欧拉是如何将这生活的趣味问题转化为数学问题的呢？又是如何证明要想一次走过这七座桥是不可能的呢？欧拉的方法十分巧妙：他用点A、B、C、D表示哥尼斯堡城的四个地区B（岛区）、C（北区）、A（东区）、D（南区）；七座桥看成这四个点的连线，用f，d，a，c，b，e，g七个数字表示,如图3-1。