单元七 · 了解更多的算法
第25课 有趣的七桥问题
一、学习目标
- 认识哥尼斯堡七桥问题，能够通过分析问题抽取关键要素进行判断处理。
- 知道哥尼斯堡七桥问题本质上是能否实现一笔画的问题，认识实现一笔画的判断方法。
二、情境导入
18 世纪初普鲁士的哥尼斯堡，有一条河穿过，河上有两个小岛，一共有七座桥连接这两座小岛和河两岸。当地居民和游客都想尝试做到这样一件事：从一个地点出发，走过这七座桥，再返回起点，而且每座桥只经过一次。这就是经典的「哥尼斯堡七桥问题」。
想一想：居民和游客都想尝试的「哥尼斯堡七桥问题」能否实现？
三、核心讲解
本课学习路径：
1认识哥尼斯堡七桥问题
2图形的一笔画分析
1．认识哥尼斯堡七桥问题
抽取对象：任务中一共有两类描述对象——桥，以及用桥连接的陆地（岛、两岸）。桥一共有 7 座，陆地共有 4 块。
从任意一个地点出发，每座桥只经过 1 次，回到起点。根据给定的图形，你是否能够画出一条每条边都只通过一次、最后还回到起点的路径呢？
欧拉依靠他深厚的数学功底，经过大约一年的研究，于 1736 年递交了题为《哥尼斯堡七座桥》的论文，回答了这一问题。欧拉认为：人们关心的只是一次不重复地走遍这七座桥，而并不关心桥的长短和岛的大小。
问题的结论：如果想从一个点出发，经过所有的边，而且每条边只经过一次，再回到起点，那么每个点连接的边数必须是偶数。然而，这个图上所有的点连接的边数都是奇数，因此哥尼斯堡七桥问题是无解的，不可能实现。
2．图形的一笔画分析
七桥问题实际上可以转化为一个几何图形能否一笔画出的问题。一笔画主要指从图形的一个点出发，笔不离开图形的线条，连续画出整个图形，而且每条线条只能画一次，不能重复。
- 首先，能够实现一笔画的图形应该是连通图形。
- 奇点：与奇数条边相连的点；偶点：与偶数条边相连的点。
规律总结：（1）奇点个数为 0 的连通图形，通常能实现一笔画，起点和终点可以是同一点。（2）奇点数为 2、偶点数为任意数的连通图形，通常也能实现一笔画，需从一个奇点出发，在另一个奇点结束，不能回到出发点。
一笔画在城市规划、道路网络设计、迷宫游戏设计等领域都有应用。
弄清以上要点后，再进入下方 Python Online，统计奇度数点判断能否一笔画。
四、动手体验 · Python 3 Online 编程
五年级 · 七桥：统计奇度数点。
正在载入 Python 3 Online
正在载入编程环境…
五、课堂总结
- 一笔画是一个经典数学问题：要确定一个图形是否可以一笔连续不断地绘制出来，且线条在绘制过程中不允许重复经过任何已绘制的线条。
- 通过分析问题、抽取关键要素进一步分析，延续了前面所学的问题分解思想——把大问题分解为局部小问题来解决。
- 对经典算法问题多分析、多思考，有助于提高算法应用能力。
六、拓展提升
- 一辆洒水车要给某城市的街道洒水。请为洒水车设计一条洒水路线，使洒水车能走过所有道路，但不重复走任何街道，还能回到出发点。
测评
选出后点「检查」。答错会显示简短说明。
哥尼斯堡七桥问题能否实现「每座桥只走一次并回到起点」？
哥尼斯堡七桥问题本质上是什么问题？
关于一笔画的判断，下列说法正确的是？
本节小结
哥尼斯堡七桥问题无解，因为全是奇点；一笔画问题要先看是否连通，再数奇点个数。欧拉的分析体现了「抽取关键要素、分解问题」的算法思想。