
_START_ARTICLE_
一笔画问题
_START_PARAGRAPH_
一笔画问题（Eulerian graph）是图论中一个著名的问题。一笔画问题起源于柯尼斯堡七桥问题。数学家欧拉在他1736年发表的论文《柯尼斯堡的七桥》中不仅解决了七桥问题，也提出了一笔画定理，顺带解决了一笔画问题。一般认为，欧拉的研究是图论的开端。_NEWLINE_与一笔画问题相对应的一个图论问题是哈密顿路径问题。
_START_SECTION_
问题的提出
_START_PARAGRAPH_
一笔画问题是柯尼斯堡问题经抽象化后的推广，是图遍历问题的一种。在柯尼斯堡问题中，如果将桥所连接的地区视为点，将每座桥视为一条边，那么问题将变成：对于一个有着四个顶点和七条边的连通图 ，能否找到一个恰好包含了所有的边，并且没有重复的路径。欧拉将这个问题推广为：对于一个给定的图，怎样判断是否存在着一个恰好包含了所有的边，并且没有重复的路径？这就是一笔画问题。用图论的术语来说，就是判断这个图是否是一个能够遍历完所有的边而没有重复。这样的图现称为欧拉图。这时遍历的路径称作欧拉路径（一个环或者一条链），如果路径闭合（一个圈），则称为欧拉回路。_NEWLINE_一笔画问题的推广是多笔画问题，即对于不能一笔画的图，探讨最少能用多少笔来画成。
_START_SECTION_
一笔画定理
_START_PARAGRAPH_
对于一笔画问题，有两个判断的准则，它们都由欧拉提出并证明。
_START_SECTION_
定理二
_START_PARAGRAPH_
如果连通无向图 有  个奇顶点，那么它可以用 笔画成，并且至少要用 笔画成。_NEWLINE_证明：_NEWLINE_将这 个奇顶点分成 对后分别连起，则得到一个无奇顶点的连通图。由上知这个图是一个环，因此去掉新加的边后至多成为 条欧拉路径，因此必然可以用 笔画成。但是假设全图可以分为 条欧拉路径，则由定理一知，每条链中只有不多于两个奇顶点，于是 。因此必定要 笔画成。
_START_SECTION_
七桥问题
_START_PARAGRAPH_
右图一是七桥问题抽象化后得到的模型，由四个顶点和七条边组成。注意到四个顶点全是奇顶点，由定理一可知无法一笔画成。
_START_SECTION_
一个可以一笔画的例子
_START_PARAGRAPH_
图二是中文“串”字抽象化后得到的模型。由于只有最上方和最下方的顶点是奇顶点，由定理一知它可以一笔画成。
_START_SECTION_
一笔画问题与哈密顿问题
_START_PARAGRAPH_
一笔画问题讨论的是能否不重复地遍历一个图的所有边，至于其中有否顶点的遍历或重复经过则没有要求。哈密顿问题讨论的则是顶点的遍历：能否不重复地遍历一个图的所有顶点？哈密顿问题由哈密顿在1856年首次提出，至今尚未完全解决。