一笔画问题的数学解释

发布时间：2020-01-06 13:40:24 河北公务员考试网来源：华图教育

　　一笔画问题的数学解释由河北公务员考试网考试快讯栏目提供，更多关于公务员考试,公务员招聘,一笔画问题口诀,河北公务员考试考试快讯的内容，请关注河北公务员考试网/河北人事考试网！

　　1 问题的提出

　　2 一笔画定理

　　2.1 定理一

　　2.2 定理二

　　3 例子

　　3.1 七桥问题

　　3.2 一个可以一笔画的例子

　　4 一笔画问题与哈密顿问题

　　5 参见

　　6 参考来源

　　问题的提出

　　一笔画问题是柯尼斯堡问题经抽象化后的推广，是图遍历问题的一种。在柯尼斯堡问题中，如果将桥所连接的地区视为点，将每座桥视为一条边，那么问题将变成：对于一个有着四个顶点和七条边的连通图 G(S,E)，能否找到一个恰好包含了所有的边，并且没有重复的路径。欧拉将这个问题推广为：对于一个给定的连通图，怎样判断是否存在着一个恰好包含了所有的边，并且没有重复的路径?这就是一笔画问题。用图论的术语来说，就是判断这个图是否是一个能够遍历完所有的边而没有重复。这样的图现称为欧拉图。这时遍历的路径称作欧拉路径(一个圈或者一条链)，如果路径闭合(一个圈)，则称为欧拉回路[1]。

　　一笔画问题的推广是多笔画问题，即对于不能一笔画的图，探讨最少能用多少笔来画成。

　　一笔画定理

　　对于一笔画问题，有两个判断的准则，它们都由欧拉提出并证明[1]。

　　定理一

　　有限图 G 是链或圈的充要条件是：G为连通图，且其中奇顶点的数目等于0或者2。有限连通图 G 是圈当且仅当它没有奇顶点[2]。

　　证明[2][3]：

　　必要性：如果一个图能一笔画成，那么对每一个顶点，要么路径中“进入”这个点的边数等于“离开”这个点的边数：这时点的度为偶数。要么两者相差一：这时这个点必然是起点或终点之一。注意到有起点就必然有终点，因此奇顶点的数目要么是0，要么是2。

　　充分性：

　　如果图中没有奇顶点，那么随便选一个点出发，连一个圈 C1。如果这个圈就是原图，那么结束。如果不是，那么由于原图是连通的，C1 和原图的其它部分必然有公共顶点s1。从这一点出发，在原图的剩余部分中重复上述步骤。由于原图是有限图，经过若干步后，全图被分为一些圈。由于两个相连的圈就是一个圈，原来的图也就是一个圈了。

　　如果图中有两个奇顶点 u 和 v，那么加多一条边将它们连上后得到一个无奇顶点的有限连通图。由上知这个图是一个圈，因此去掉新加的边后成为一条链，起点和终点是 u 和 v。

　　定理二

　　如果有限连通图 G 有2k个奇顶点，那么它可以用 k 笔画成，并且至少要用 k 笔画成[2]。

　　证明[2][3]：将这2k个奇顶点分成 k 对后分别连起，则得到一个无奇顶点的有限连通图。由上知这个图是一个圈，因此去掉新加的边后至多成为 k 条链，因此必然可以用 k 笔画成。但是假设全图可以分为 q 条链，则由定理一知，每条链中只有两个奇顶点，于是。因此必定要 k 笔画成。

　　例子

　　图一：无法一笔画

　　图二：尽管按照中文书写习惯“串”字不止一笔，但它可以一笔写成。七桥问题

　　右图一是七桥问题抽象化后得到的模型，由四个顶点和七条边组成。注意到四个顶点全是奇顶点，由定理一可知无法一笔画成。

　　一个可以一笔画的例子

　　图二是中文“串”字抽象化后得到的模型。由于只有最上方和最下方的顶点是奇顶点，由定理一知它可以一笔画成。

　　一笔画问题与哈密顿问题

　　一笔画问题讨论的是能否不重复地遍历一个图的所有边，至于其中有否顶点的遍历或重复经过则没有要求。哈密顿问题讨论的则是顶点的遍历：能否不重复地遍历一个图的所有顶点?[4]哈密顿问题由哈密顿在1856年首次提出，至今尚未完全解决[2]。