欧拉七桥问题

1、欧拉的七桥问题本章内容 一、欧拉问题的来源和解决办法 二、哈密顿图 三、图论 四、数据结构和图论以及图论在计算机方面的应用 五、小结哥尼斯堡城七桥问题发现问题 18世纪初普鲁士的哥尼斯堡，有一条河穿过，河上有两个小岛，有七座桥把两个岛与河岸联系起来 (如图)。问是否可能从这四块陆地中任一块出发，恰好通过每座桥一次，再回到起点？这就是著名的“哥尼斯堡七桥问题”。思考问题 欧拉发现七桥问题仅仅涉及物体的位置关系，而与路程无关，于是他把“哥尼斯堡七桥问题”转化成一个几何问题，用点A，C表示岛屿，点B，D表示河的两岸，用连接两点的线表示桥。解决问题 若一个顶点发出的弧的条数为奇数时，称为奇顶点；发生的

2、弧的 条数为偶数时，称为偶顶点，一笔画一定有一个起点、一个终点和一定数目的通过点，分两种情况考虑： 第一种：起点和终点不是同一点，把集中在起点的所有弧画完为止，有进有出，最后一笔必须画出去，所以起点必须是奇顶点；另一方面把集中在终点的所有弧线画完为止，最后一笔必须画进来，因此，终点也必须是奇顶点；其它经过的点，有几条弧画进来，必有同样多的弧画出去，必是偶顶点。 第二种：起点和终点为同一点，又画出去，又画进来，必为偶顶点，其它顶点有进有出也都是偶顶点。解决问题因此，欧位得出以下结论： 1.全是偶顶点的网络可以一笔画。2.能一笔画的网络的奇顶点数必为0或2。3.如果一个网络有两个奇顶点，它就可以一

3、笔画，但最后不能回到原来的出发点，这时，必须从一个奇顶点出发，然后回到另一个奇顶点。用欧拉的发现去分析七桥问题，这张图上的A、B、C、D全是奇顶点，因此，不能一笔画，所以，游人一次走遍七桥是不可能的。我们发现 凡是由偶点组成的连通图，一定可以一笔画成。画时可以把任一偶点为起点，最后一定能以这个点为终点画完此图。 凡是只有两个奇点的连通图（其余都为偶点），一定可以一笔画成。画时必须把一个奇点为起点，另一个奇点为终点。 其他情况的图都不能一笔画出。(奇点数除以二便可算出此图需几笔画成。) 欧拉问题放在七桥问题上则是能否可以不重复地走完七个桥，如何走的问题当然这只是一个例子，他代表的是一种思维方式，

4、一门新的学课思想。那就是图论。 欧拉问题其实就是一个一笔画问题。 这时就有人要问怎么能一笔画呢，在图论中一笔画的问题交给了图论里的另一个重要研究问题即是哈密顿图，哈密顿图则是给出我们最优过程或者最优解的一种抽象的研究方法。 欧拉问题促进了图论的诞生而哈密顿图则是对图论的发展和补充。哈密顿图 1859年，英国数学家哈密顿发明了一种游戏：用一个规则的实心十二面体，它的20个顶点标出世界著名的20个城市，要求游戏者找一条沿着各边通过每个顶点刚好一次的闭回路，即“绕行世界”。用图论的语言来说，游戏的目的是在十二面体的图中找出一个生成圈。这个生成圈后来被称为汉密尔顿回路。这个问题后来就叫做汉密尔顿问题。

5、由于运筹学、计算机科学和编码理论中的很多问题都可以化为汉密尔顿问题，从而引起广泛的注意和研究。哈密顿图定义 设G=(P,L)是有向图，（ v1 1, vn n）是G中一条路，如果G中没每点在此路中出现一次，则称此路为哈密顿路。如果G中每点除v1 1外，恰在此路中出现一次，且v1 1 vn n，则此路称为哈密顿回路。定义 设G=(P,L)是有向图，如果G中有一条哈密顿回路，则称G为哈密顿图。G1哈密顿图 在图中，路（ABCDHGFE）是哈密顿路。路（ABCDHGFEA）是哈密顿回路。G1HGFEDCBAG2 2哈密顿图哈密顿路是遍历图的所有点。 对于哈密顿路与哈密顿回路，下面的一些性质是显然的。

6、 哈密顿路是简单路。设G有n个点，这G的哈密顿路有n-1条边，G的哈密顿回路有n条边。 若G中某点度是0，这G既无哈密顿路，也无哈密顿回路。若G中某点的度是1，这G无哈密顿回路。 设v是G中的一个点， dG G(v)=2若G有哈密顿回路，则以v为端点的两边必须都出现在哈密顿回路中。 哈密顿回路要求遍历诸点，如果图中某些必须在哈密顿回路中出现的边已经构成回路，而图中尚有不在该回路中出现的点，这该图一定没有哈密顿回路。 设v是图G的一个点，dG G(v) 2，G有哈密顿回路，则哈密顿回路仅使用以v为端点的两条边。欧拉图、哈密顿图与图论 我们看看一笔画问题牵扯着计算里的算法和可计算性 欧拉问题放在七

7、桥问题上则是能否可以不重复地走完七个桥，如何走的问题当然这只是一个例子，他代表的是一种思维方式，一门新的学课思想。那就是图论。 这是就有人要问那么能一笔画的问题呢，在图论中一笔画的问题交给了图论里的另一个重要研究问题即是哈密顿图，哈密顿图则是给出我们最优过程或者最优解的一种抽象的研究方法。 欧拉问题促进了图论的诞生而哈密顿图则是对图论的发展和补充。图论 图：图是一种抽象的数据结构 图论：它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。 图论在数据结构、数据库、网络

8、技术、程序设计等课程中都有广泛应用，成为计算机科学与应用技术中必不可少的一部分。而图论的研究起源于“哥尼斯堡城七桥问题”，欧拉成为图论的奠基人。数据结构与图论“数据结构”的研究不仅涉及到计算机硬件（特别是编码理论、存储装置和存取方法）的研究范围，而且和计算机软件的研究有着更为密切的关系。数据结构：计算机处理的对象之间通常存在着的是一种最简单的线性关系，这类数学模型可称为线性的数据结构，简单地来说，数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的科学。在计算机面向对象的编程中，我们常常将具体事物抽象为类，从而研究类的属性，然而类的属性则不单单只是简单的外在属性的描述，更为重要的是它同其他类之间的内在逻辑关系，或者说是线性关系。可见数据结构则是支撑这一理论的根据。然而又是什么东西在支撑着数据结构呢，我们从以上分析中不难看出图论是其中很重要的一部分。图论与计算机的关系 图论是一门古老的数学分支，它起源于游戏难题的研究，如1736年欧拉所解决的哥尼斯堡七桥问题，以及迷宫问题、博弈问题、棋盘上马的行走路线问题等。 同时，图论又是近年来发展迅速且应用广泛的一门新兴学科，已渗透到诸如语言学、物理学、化学、电讯工程、计算机科学以及数学的其它分支中，特别在计算机科学中，如形式语言、数据结构