一笔画问题

一笔画问题（Eulerian graph）是图论中一个著名的问题。一笔画问题起源于柯尼斯堡七桥问题。数学家欧拉在他1736年发表的论文《柯尼斯堡的七桥》中不仅解决了七桥问题，也提出了一笔画定理，顺带解决了一笔画问题。一般认为，欧拉的研究是图论的开端。

与一笔画问题相对应的一个图论问题是哈密顿路径问题。

能夠在不重複折返的前提下一笔画寫出或一次走完該路徑的條件，是文字、圖形、路徑的奇顶点的數目正好是0個或2個時，而如果奇顶点的數目兩個時，必須正好為起點或終點，奇顶点是指該點延展出奇數數目的方向，例如T字路口延展出三條道路方向，而線段的端點也是只有一個方向的奇顶点

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

证明：

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

*# 如果图中没有奇顶点，那么随便选一个点出发，连一个环C_1。如果这个环就是原图，那么结束。如果不是，那么由于原图是连通的，C_1 和原图的其它部分必然有公共顶点 s_1。从这一点出发，在原图的剩余部分中重复上述步骤。由于原图是连通图，经过若干步后，全图被分为一些环。由于两个相连的环就是一个环，原来的图也就是一个欧拉环了。
*# 如果图中有两个奇顶点 u 和 v，那么加多一条边将它们连上后得到一个无奇顶点的连通图。由上知这个图是一个环，因此去掉新加的边後成为一条路径，起点和终点是 u 和 v。证毕。

连通无向图有欧拉路径的充要条件也可以写作“图中奇顶点数目不多于2个”，这是因为奇顶点数目不可能是1个。实际上，连通无向图中，奇顶点的数目总是偶数。

对于不连通的无向图，如果有两个互不连通的部分都包含至少一条边，那么显然不能一笔画。只有当此图的边全都在某一个连通部分中（即其它的连通部分都是一个个孤立的顶点，度数为0），并满足连通无向图关于一笔画的充要条件，而该图才能一笔画。也即是说，可以一笔画的（无向）图如果不是连通图，就必定是一个可以一笔画的连通图与若干个孤立顶点的组合。

除了用顶点的度数作为判定的充要条件，还可以用图中边的特性来作为欧拉回路存在的判定准则。连通的无向图 G中存在欧拉回路，等价于图G所有的边可以划分为若干个环的不交并。具体来说，等价于存在一系列的环C_1, C_2 , \cdots , C_m，使得图G里的每一条边都恰好属于某一个环。

定理二
如果连通无向图 G 有 2k 个奇顶点，那么它可以用 k 笔画成，并且至少要用 k 笔画成哈密顿问题由哈密顿在1856年首次提出，至今尚未完全解决。

参见

• 柯尼斯堡七桥问题
• 哈密尔顿问题
• 树 (圖論)
• 中国邮递员问题

参考来源