三年级奥数：从哥尼斯堡七桥问题谈起2013

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。

三年级奥数讲座（二）目录第一讲从数表中找规律第二讲从哥尼斯堡七桥问题谈起第三讲多笔画及应用问题第四讲最短路线问题第五讲归一问题第六讲平均数问题第七讲和倍问题第八讲差倍问题第九讲和差问题第十讲年龄问题第十一讲鸡兔同笼问题第十二讲盈亏问题第十三讲巧求周长第十四讲从数的二进制谈起第十五讲综合练习第一讲从数表中找规律在前面学习了数列找规律的基础上，这一讲将从数表的角度出发，继续研究数列的规律性。

例1 下图是按一定的规律排列的数学三角形，请你按规律填上空缺的数字.分析与解答这个数字三角形的每一行都是等差数列（第一行除外），因此，第5行中的括号内填20，第6行中的括号内填 24。

例2 用数字摆成下面的三角形，请你仔细观察后回答下面的问题：①这个三角阵的排列有何规律？②根据找出的规律写出三角阵的第6行、第7行。

③推断第20行的各数之和是多少？分析与解答①首先可以看出，这个三角阵的两边全由1组成；其次，这个三角阵中，第一行由1个数组成，第2行有两个数…第几行就由几个数组成；最后，也是最重要的一点是：三角阵中的每一个数（两边上的数1除外），都等于上一行中与它相邻的两数之和.如：2=1+1，3=2+1，4=3+1，6=3＋3。

②根据由①得出的规律，可以发现，这个三角阵中第6行的数为1，5，10，10，5，1；第7行的数为1，6，15，20，15，6，1。

③要求第20行的各数之和，我们不妨先来看看开始的几行数。

至此，我们可以推断，第20行各数之和为219。

[本题中的数表就是著名的杨辉三角，这个数表在组合论中将得到广泛的应用]例3将自然数中的偶数2，4，6，8，10…按下表排成5列，问2000出现在哪一列？分析与解答方法1：考虑到数表中的数呈S形排列，我们不妨把每两行分为一组，每组8个数，则按照组中数字从小到大的顺序，它们所在的列分别为B、C、D、E、D、C、B、A.因此，我们只要考察2000是第几组中的第几个数就可以了，因为2000是自然数中的第1000个偶数，而1000÷8＝125，即2000是第125组中的最后一个数，所以，2000位于数表中的第250行的A列。

数据结构课程设计题目：哥尼斯堡的“七桥问题”院系：班级：学号：姓名：2014-2015年度第1学期哥尼斯堡的“七桥问题”一．题目：哥尼斯堡的“七桥问题”二．设计目标帮助学生熟练掌握图和邻接表的使用，了解利用图能够解决生活中的那些实际问题。

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

问是否可能从这四块陆地中任一块出发，恰好通过每座桥一次，再回到起点?四．概要设计1>构建用邻接表存储的图结构体：2> 图的初始化3> 读入并存储一个图G4>图G的深度优先搜索5>检查边的度是否全为偶数五．详细设计（给出算法的伪码描述和流程图）总体操作步骤：流程图设计：主流程图：1>构建用邻接表存储的图结构体：typedef struct {int Visited[MAXV]; /* 顶点标记*/int Edges[MAXV][MAXV]; /* 邻接表*/int VertexN, EdgeN; /* 顶点和边数*/} Graph;2>图的初始化：3>读入并存储一个图G4>图G的深度优先搜索:5>检查边的度是否全为偶数:6>主函数：代码分析：1>图的初始化：void InitializeG ( Graph *G ){int i, j;for (i=0; i<MAXV; i++){for (j=0; j<MAXV; j++)G->Edges[i][j] = 0;G->Visited[i] = 0;}G->VertexN = G->EdgeN = 0;}2>读入并存储一个图G:void ReadG ( Graph *G ){ /* 读入并存储一个图G */int i, V1, V2;scanf("%d %d", &G->VertexN, &G->EdgeN);for (i=0; i<G->EdgeN; i++){scanf("%d %d", &V1, &V2);G->Edges[V1-1][V2-1] = G->Edges[V2-1][V1-1] = 1;}}3>图G的深度优先搜索:void DFS ( Graph *G, int V ){ /* 图G的深度优先搜索*/int W;G->Visited[V] = 1; /* 将访问到的结点进行标记*/for (W=0; W<G->VertexN; W++)if (G->Edges[V][W] && !G->Visited[W])DFS(G, W);}4>检查边的度是否全为偶数:int CheckG ( Graph *G ){ /* 检查边的度是否全为偶数*/int r, i, j;for (i=0; i<G->VertexN; i++){r = 0;for (j=0; j<G->VertexN; j++)r += G->Edges[i][j];if (r%2) return 0; /* 发现奇数度的边则返回0 */}return 1; /* 全是偶数度的边则返回1 */}5>主函数：int main(){int i;Graph *G = malloc( sizeof(Graph) );InitializeG( G );ReadG( G );DFS( G, 0 ); /* 检查连通性*/for (i=0; i<G->VertexN; i++)if (!G->Visited[i])break;if (i<G->VertexN) /* 若有结点没被DFS访问到*/printf("0\n"); /* 则图不连通*/else /* 若图连通*/printf("%d\n", CheckG(G));return 0;}六．测试分析白盒：查看代码完整性黑盒：测试是否可以正确的创建，删除，插入，打印，查找等操作七．使用说明插入删除语句：删除1条内容插入语句：插入一条信息自动打印：打印内容八．测试数据注：学生在测试数据时，需要写出测试用例和截图十．课程设计总结通过“哥尼斯堡的“七桥问题””这个题目，我认识到了图的使用，以及邻接表存储。

哥尼斯堡七桥哥尼斯堡七桥问题也叫做欧拉七桥问题，曾经悬而未解，后得以被数学家欧拉证明。

欧拉曲线也是从七桥问题开始的。

相传在哥尼斯堡这座古老的城市有一个传说，有两条河流在这里交汇，将这座城市分成了四个部分，居民于是在城里造了七座桥将这四个部分连接起来，便利了这里的交通。

但也由此产生了一个疑问，城市里有没有一种路线能一次走完所有的桥，并且每座桥都只走一次。

这个问题难倒了当时所有的市民，同时也引来的欧拉的观注。

欧拉作为一个数学家，以他独有的方式将桥梁跟陆地看成是由点和线连起来的一个图，能不能一次走完七座桥就变成了能不能一笔画完这个图的问题。

如果这个图能够一笔画完，一定存在一个终点和起点，而除去终点和起点，只看中间将会经过的点，欧拉的认为，每通过一条线进入一个点，必定还有一条线能离开这个点，这样进入的线与出去的线肯定相等，也就是说，连接这些点的线必将是偶数。

而在欧拉设想的这个图中，每个点的相邻的线都是奇数，所以不可能一笔画完这个图，一次走完七座桥的路线也就不存在。

欧拉将对此问题的研究化为了一个几何问题，这种几何区别于以前的几何主要是交点的位置、线段的长短甚至它们的面积都不重要，重要的是点、线之间的相关关系，这就是数学上图论的先河。

可见，对数学问题的研究，甚至大到数学学科的开创，也是从生活实践中得来的，生活中何尝又不存在真理呢？反观欧拉曲线，其中每次所画的线都符合上述欧拉的观点，不同的是，曲线不一定是闭合的，甚至就是一条直线也有可能，终点和起点也不一定是同一个点。

事实上，如果能一笔画完一条曲线，那么这条曲线包含奇数条边的点的数目不是0就是2，如果点连接的边都是偶数的话终点与起点肯定在同一个点上，并且可以任选一个点作为终点和起点一笔画完，而如果有两个点连接的边是奇数，那么终点跟起点就在这两个点上，要一笔画完这条曲线，必定是从其中一个奇数点开始，终止于另一个奇数点。

欧拉曲线，你会玩了吗？。

哥尼斯堡七桥问题探究欧拉对于《哥尼斯堡桥》一文进行了深入分析与研究，解开了“哥尼斯堡七桥问题”所蕴含的丰富数学思想。

通过对七桥问题进行研究与分析，能够让我们对于数学领域中的相关知识予以深入掌握，带给我们更为丰富的数学视角与视野。

标签：哥尼斯堡桥七桥问题欧拉数学思想一、哥尼斯堡七桥问题简述“七桥问题”出现于18世纪哥尼斯堡城。

在这个城市中有七座桥，当时居民十分热衷：一个散步者怎样将这七座桥走遍，并且每座桥都不重复。

要想符合所提出的要求，应当与以下两个条件相适应：第一，所谓的“不重复”指的是，每座桥只能走一次；第二，所谓的“走遍”指的是，每座桥都应当走到不应当被落下。

这些问题的解决是欧拉所完成的，在很多的文献资料中，都提到了欧拉对七桥问题解决的方法，实际上，在欧拉的论文《问题解决与几何位置》中，只包括以下的三幅图与两个表格。

该问题主要包括两个特征：第一，该问题全部来源于现实；第二，该问题属于新数学领域范畴，欧拉的解答所具备的创新性非常突出，对数学教育工作的开展具有至关重要的启发作用。

二、欧拉对七桥问题的解答第一步就是，对描述路线的简洁方法进行寻找。

将河流分割的陆地区域分别用A、B、C 、D表示，地点A到达地点B需要对桥a或b进行跨越，记作AB，倘若再从地点B跨越桥f到达地点D，记作ABD，字母B不仅代表首次跨越的终点，也代表第二次跨越的起点，其余地点也根据这种方法进行类推。

其发现：第一，该表示方法与跨越的桥不存在任何关联；第二，跨越n座桥的路线正好可以用n+1个字母来代表。

该问题就转变成符合条件的八个字母排列问题。

在部分区中，所连接的桥不止一座，部分字母会多次出现，所以，应当对每个字母所出现的次数进行确定。

为了对某个字母出现次数的法则进行判定，欧拉选取单独的区域A，并对多座桥进行随意设置，散步者可以利用不同的桥离开或进入A，所通过的桥数决定着字母A出现的次数，倘若桥数为奇数，表1将其规律进行了揭示，也就是桥数加1的和再除以2，就是字母A所出现的次数。

哥尼斯堡七桥问题
18世纪在哥尼斯堡城(今俄罗斯加里宁格勒)的普莱格尔河上有7座桥，将河中的两个岛和河岸连结，如图1所示。

城中的居民经常沿河过桥散步，于是提出了一个问题：能否一次走遍7座桥，而每座桥只许通过一次，最后仍回到起始地点。

这就是七桥问题，一个著名的图论问题。

这个问题看起来似乎不难，但人们始终没有能找到答案，最后问题提到了大数学家欧拉那里。

欧拉以深邃的洞察力很快证明了这样的走法不存在。

欧拉是这样解决问题的：既然陆地是桥梁的连接地点，不妨把图中被河隔开的陆地看成A 、B 、C 、D4个点，7座桥表示成7条连接这4个点的线，如图2所示。

于是“七桥问题”就等价于图3中所画图形的一笔画问题了。

欧拉注意到，每个点如果有进去的边就必须有出来的边，从而每个点连接的边数必须有偶数个才能完成一笔画。

图3的每个点都连接着奇数条边，因此不可能一笔画出，这就说明不存在一次走遍7座桥，而每座桥只许通过一次的走法。

欧拉对“七桥问题”的研究是图论研究的开始，同时也为拓扑学的研究提供了一个初等的例子。

图3
图2 图1。