一笔画问题(Eulerian graph)是图论中一个著名的问题。一笔画问题起源于哥尼斯堡七桥问题。数学家欧拉在他1736年发表的论文《哥尼斯堡的七桥》中不仅解决了七桥问题,也提出了一笔画定理,并解决了一笔画问题。[1] 一笔画问题的规律是凡是由偶点组成的连通图,一定可以一笔画成,画时可以把任一偶点为起点,最后一定能以这个点为终点一笔画完此图,还有凡是只有两个奇点的连通图(其余都为偶点),一定可以一笔画成,画时必须把一个奇点为起点,另一个奇点为终点。[2] 一笔画在生活中也有着重要的应用,比如洒水车进行清洗马路的工作,会设计一种科学的走法,使它既能完成洒水任务,又可以不重复地走过每条街道。[3]
定义
众所周知的“哥尼斯堡城‘七桥问题’”被大数学家欧拉开创了数学新分支-----图论。也就是“一笔画”。一笔画图形的必要条件是:奇点数目是0或者2。图⑴的“七桥问题”A,B,C,D都是奇节点,数目是4,所以不能够“一笔画”。我们把节点转换回来,成为“节面”(区域),来考虑“一笔画”。