七桥问题 豪 问题 A 令寻找走遍哥尼斯堡( KOnigsberg) 岛 城的7座桥,且只许走过每座桥 次,最后又回到原出发点 口求解 ◆1736年瑞士大数学家欧拉 ( Leonhard euler)发表了关于 “哥尼斯堡七桥问题”的论文 (图论的第一篇论文)。他指出 从一点出发不重复的走遍七桥, 最后又回到原来出发点是不可能 的
2 七桥问题 ❑问题 ❖寻找走遍哥尼斯堡（KÖnigsberg） 城的7座桥，且只许走过每座桥一 次，最后又回到原出发点 ❑求解 ❖1736年瑞士大数学家欧拉 （Leonhard•Euler）发表了关于 “哥尼斯堡七桥问题”的论文 （图论的第一篇论文）。他指出 从一点出发不重复的走遍七桥， 最后又回到原来出发点是不可能 的
图论 豪 图论是近年来发展迅速而又应用广泛的 门新兴学科。它最早起源于一些数学游戏的 难题研究,如1736年欧拉( LEuler)所解决 的哥尼斯堡七桥问题。以及在民间广为流传 的一些游戏问题:例如迷宫问题、棋盘上马 的行走路线问题
3 图论 图论是近年来发展迅速而又应用广泛的一 门新兴学科。它最早起源于一些数学游戏的 难题研究，如1736年欧拉（L.Euler)所解决 的哥尼斯堡七桥问题。以及在民间广为流传 的一些游戏问题：例如迷宫问题、棋盘上马 的行走路线问题
棋盘上马的行走路线问题 豪 口在中国象棋中,马走“日”字,即每步从1×2矩形的 个顶点跳到相对的顶点。如图,马从M(3,2)一次只 能跳到A、B、C、D、E、F、G、H中的任何一个位置。 口问题:马能否从棋盘上任意一点出发,不重复、不遗漏 地走遍整个棋盘(即每一点都走到并且只到一次)? 楚河汉界 H B G 马 D 12345 78 4
4 棋盘上马的行走路线问题 ❑ 在中国象棋中，马走“日”字，即每步从1×2 矩形的一 个顶点跳到相对的顶点。如图，马从M（3，2）一次只 能跳到A、B、C、D、E、F、G、H中的任何一个位置。 ❑ 问题：马能否从棋盘上任意一点出发，不重复、不遗漏 地走遍整个棋盘（即每一点都走到并且只到一次）？
棋盘上马的行走路线问题 豪 口将马目前所在位置涂成白色,用涂色的方法,将棋 盘上的点分为黑、白相间的两类 楚河汉界 3 1 7 8
5 棋盘上马的行走路线问题 ❑ 将马目前所在位置涂成白色，用涂色的方法，将棋 盘上的点分为黑、白相间的两类
环游世界各国的问题 豪 口英国数学家哈密顿于1859年以游戏的形式提出:把一个 正十二面体的二十个顶点看成二十个城市,要求找出 条经过每个城市恰好一次而回到出发点的路线。这条路 线就称“哈密顿圈”。一百多年来,对哈密顿问题的研 究,促进了图论的发展。 16 5 14
6 环游世界各国的问题 ❑ 英国数学家哈密顿于1859年以游戏的形式提出：把一个 正十二面体的二十个顶点看成二十个城市，要求找出一 条经过每个城市恰好一次而回到出发点的路线。这条路 线就称“哈密顿圈”。一百多年来，对哈密顿问题的研 究，促进了图论的发展