挑战≈ 15 分钟未开始
一笔画与欧拉路径
核心概念
一笔画(欧拉路径):笔不离纸、每条边恰好走一次,把整个图画完。
欧拉判定定理(对连通图):
- 存在欧拉回路(起点终点相同) 所有顶点的度都是偶数;
- 存在欧拉路径(起点终点可不同) 恰有 个或 个奇数度顶点;
- 若奇数度顶点超过 个,则无法一笔画。
当恰有 个奇点时,一笔画必须以这两个奇点分别作为起点和终点。
直观理解 · 动手试试
为什么奇点是关键?想象一次性走完所有边。对于路径中间经过的每个点,你"走进来"一次就得"走出去"一次,边总是成对使用,所以中间点的度必须是偶数。只有起点和终点可以"落单"——起点先出不进、终点只进不出。
于是:没有奇点 → 可以从任意点出发绕一圈回来(欧拉回路);恰好两个奇点 → 必须从一个奇点走到另一个奇点(欧拉路径);奇点多于两个 → 无论如何都有点"卡住",画不成。这就是柯尼斯堡七桥问题的答案:四块陆地都是奇数度,无法一笔画。
一笔画 · 欧拉
能否一笔画？
奇数度顶点(红色)共 0 个 → 存在欧拉回路(可从任意点出发绕回)
圆圈里的数字是该点的度,红色表示奇数度。一笔画的判据:奇点为 0 个(回路)或 2 个(路径),否则不行。
某图有 个顶点,度数为 。能否一笔画?
▸查看解答步骤
答: 能,以两个奇点为起终点
柯尼斯堡七桥:四块陆地两两由桥相连,各陆地连出的桥数为 。能否每座桥恰好走一次?
▸查看解答步骤
答: 不能一笔画
即时练习
连通图所有顶点度都为偶数时,存在欧拉回路。
这正是欧拉回路存在的充要条件。
一个连通图能一笔画(但起点终点不同),它最多有几个奇数度顶点?
恰好 个奇点对应欧拉路径(起终点不同)。
有 个奇数度顶点的连通图可以一笔画。
奇点多于 个就无法一笔画。
度数为 的连通图,一笔画情况是?
存在欧拉回路(0 个奇点)只有欧拉路径,起终点不同无法一笔画无法判断全是偶数度, 个奇点,存在欧拉回路,可从任意点出发绕回。
恰有 个奇点的图一笔画时,起点应选在?
某个奇数度顶点任意偶数度顶点度最大的顶点度最小的顶点必须从一个奇点出发、到另一个奇点结束。
易错点
- 忘记"连通"前提。 欧拉判定只对连通图成立;不连通则根本无法一笔画。
- 把奇点个数 当成可行。 由奇点定理,奇点个数不可能是 ;一笔画要求是 或 。
- 起终点选错。 有 个奇点时,起点和终点必须正是这两个奇点。