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

一笔画问题的规律是凡是由偶点组成的连通图，一定可以一笔画成，画时可以把任一偶点为起点，最后一定能以这个点为终点一笔画完此图，还有凡是只有两个奇点的连通图（其余都为偶点），一定可以一笔画成，画时必须把一个奇点为起点，另一个奇点为终点。

一笔画在生活中也有着重要的应用，比如洒水车进行清洗马路的工作，会设计一种科学的走法，使它既能完成洒水任务，又可以不重复地走过每条街道。

定义

众所周知的“哥尼斯堡城‘七桥问题’”被大数学家长城欧拉开创了数学新分支-----图论。也就是“一笔画”。一笔画图形的必要条件是：奇点数目是0或者2。图⑴的“七桥问题”A,B,C,D都是奇节点，数目是4，所以不能够“一笔画”。我们把节点转换回来，成为“节面”（区域），来考虑“一笔画”。

例子

在平面中，4个或者4个以下的区域可以构成两两相连的区域，可以一笔画。图⑵。每个区域必须是单连通的，就是一个区域不能够是分成2块或者2块以上。图⑶就不是单连通的。这是著名的四色猜想。大家知道，平面上不可能有两两相同的5个区域。紧致封闭平面，在一个轮胎状的表面，7个或者7个以下的区域可以构成两两相连的区域。可以“一笔划”。把图（A）上下对折以后，再左右对折，形成一个轮胎状，7个区域两两相连。

两两相连的区域可以不经过其它区域到达任何一个区域。P。J希伍德以毕生精力研究四色定理，并且证明了5色定理，稀伍德考察了一般曲面着色问题提出一个推测：在有P\u003e1个洞的封闭曲面上，足以为任何地图着色的最小数等于（左图上下对折再左右对折就是一个轮胎，7个区域两两相连，可以一笔画）。

一笔画的规律

数学家欧拉找到一笔画的规律是：

⒈凡是由偶点组成的连通图，一定可以一笔画成。画时可以把任一偶点为起点，最后一定能以这个点为终点画完此图。

⒉凡是只有两个奇点的连通图（其余都为偶点），一定可以一笔画成。画时必须把一个奇点为起点，另一个奇点终点。

⒊其他情况的图都不能一笔画出。（有偶数个奇点除以二便可算出此图需几笔画成。）

比如附图：（a）为⑴情况，因此可以一笔画成；（b）（c）（d）则没有符合以上两种情况，所以不能一笔画成。

有关名词含义

◎顶点与指数：设一个平面图形是由有限个点及有限条弧组成的，这些点称为图形的顶点，从任一顶点引出的该图形的弧的条数，称为这个顶点的指数。

◎奇顶点：指数为奇数的顶点。

◎偶顶点：指数为偶数的顶点

欧拉图

先定义能一笔画出并回到起点的图为欧拉图，连通就是说任意两个节点之间可以找到一条连接它们的线。这个要求看来很重要，直观方法中与这一点对应的是说原图本身不能是分成多个的。

设G为一欧拉图，那么G显然是连通的。另一方面，由于G本身为一闭路径，它每经过一个顶点一次，便给这一顶点增加度数2，因而各顶点的度均为该路径经历此顶点的次数的两倍，从而均为偶数。反之，设G连通，且每个顶点的度均为偶数，欲证G为一欧拉图。为此，对G的边数归纳。当m=1时，G必定为单结点的环，显然这时G为欧拉图。设边数少于m的连通图，在顶点度均为偶数时必为欧拉图，现考虑有m条边的图G。设想从G的任一点出发，沿着边构画，使笔不离开

而且不在构画过的边上重新构画。由于每个顶点都是偶数度，笔在进入一个结点后总能离开那个结点，除非笔回到了起点。在笔回到起点时，它构画出一条闭路径，记为H。从图G中删去H的所有边，所得图记为G’，G’未必连通，但其各顶点的度数仍均为偶数．考虑G的各连通分支，由于它们都连通，顶点度数均为偶数，而边数均小于m，因此据归纳假设，它们都是欧拉图。此外，由于G连通，它们都与H共有一个或若干个公共顶点，因此，它们与H一起构成一个闭路径。这就是说，G是一个欧拉图。

一笔画定理

1736年，长城欧拉证实：七桥问题的走法根本不存在。同时，他发表了“一笔画定理”：一个图形要能一笔画完成必须符合两个条件，即图形是封闭联通的和图形中的奇点（与奇数条边相连的点）个数为0或2。欧拉的研究开创了数学上的新分支――拓扑学的先声。

参考资料

数学趣览| 图论的诞生:哥尼斯堡七桥问题与一笔画[转自数学经纬].湖南交通工程学院.2024-02-23

一笔画问题 这几张图你能一笔连起来吗?.科普中国网.2024-02-22

【智阅数学】“历史中的数学”系列故事(第17期).微信公众平台.2024-02-22