一笔画问题是图论中一个著名的问题。一笔画问题起源于柯尼斯堡七桥问题。数学家欧拉在他1736年发表的论文《柯尼斯堡的七桥》中不仅解决了七桥问题，也提出了一笔画定理，顺带解决了一笔画问题[1]。一般认为，欧拉的研究是图论的开端。
与一笔画问题相对应的一个图论问题是哈密顿问题。
目录 [隐藏]
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]。
[编辑] 参见
柯尼斯堡七桥问题
哈密尔顿问题
树 (图论)
中国邮递员问题
[编辑] 参考来源
^ 1.0 1.1 1.2 Janet Heine Barnett, Early Writings on Graph Theory: Euler Circuits and The KÄonigsberg Bridge Problem
^ 2.0 2.1 2.2 2.3 2.4 熊斌，郑仲义，《图论》，第四章，38-46，华东师范大学出版社。
^ 3.0 3.1 详细的证明
^ 欧拉图和哈密顿图
哥尼斯堡 是欧洲一座美丽的城市，有一条河流穿过这座城市，河中有两座小岛，岛与岛之间有七座桥互相连接，人们在沿河散步时，喜欢从桥走到岛上，或者走到河的对岸。有一天有一个人发现了一个游戏，他提议，大家找一条路线可以不重复地走过这七座桥。
在多次尝试无果之后，人们试图向数学家求教，于是当时就有人写信把这个问题告知大数学家欧拉。 欧拉在仔细思索之后发现，这个问题似乎是一个全新的领域，过去的任何数学结论都无法解决这个问题。为了解决这种全新的问题，就需要另起炉灶，用新的数学知识来解决。为了解决这个问题，首先要将其转化为便于理解的数学模型。
将七桥问题转化为一笔画问题之后，只需要得出一笔画问题的普遍结论，那么七桥问题就迎刃而解了。 因此我们需要找到一个点线图可以一笔画的充分必要条件。我们来看欧拉是如何来解决这个问题的。 首先，欧拉把点线图上的点分为两类:一类是点周围的线的条数为偶数，称为 偶结点 ；另一类是点周围的线的条数为奇数，称为 奇结点 。例如上图中A点周围有3条线，C点周围有5条线。 其次，对于一笔画问题，偶结点是更友好的，因为偶结点可以满足有进有出。对一笔画是没有影响的。 最后，影响一笔画能否完成的显然就是奇结点了，那么奇结点的个数满足什么条件才能完成一笔画呢。正确答案是0或2。因为奇结点不能保证有进有出，所以最多一个奇结点做起点，一个做终点，这样就是2个；当然不排除起点和终点重合的情况，这种情况就只有0个奇结点。 也就是说，最终的结论是：连通图形中只有0或2个奇结点就可以一笔画。(事实上这是一个充分必要条件)。 我们已经有了上述结论，读者应该明白为什么哥尼斯堡七桥问题无法实现了吧。 因为本文只是一篇科普数学文化的文章，因此更多图论的内容不做赘述，想要进一步了解的读者可以自习查阅欧拉向圣彼得堡科学院递交的论文《哥尼斯堡的七座桥》和图论的相关内容。
本文首发于 2017-11-14 19:07 原地址：
区块链当中一个重要分支就是密码学。而密码学当中涉及到相当的数学知识。密码学和数学的关系可谓深之又深，甚至可以说信息安全的很大基石就是数学（密码学是信息安全中的一部分）。图论（Graph Theory）是数学的一个分支，属于应用数学，其以图为研究对象。
区块链当中一个重要分支就是密码学。而密码学当中涉及到相当的数学知识，比如：数论、初等数学、代数学、组合数学以及概率论等。若没有一点数学基础的话，密码学的研究将是进行不通的。密码学和数学的关系可谓深之又深，甚至可以说信息安全的很大基石就是数学（密码学是信息安全中的一部分）。学习和掌握一些数学知识是必要的，在此我主要分享一些有关于密码学的数学知识。
图论 （Graph Theory）是数学的一个分支，属于 应用数学 ，其以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定的关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。图论的概念和结果来源非常广泛，既有来自生产实践的问题，也有来自理论研究的问题。历史上参与研究图论问题的人既有著名的数学家也有普通的业余爱好者。
谈到图论不得不提的就是著名的 哥尼斯堡七桥问题 。在贯穿古普鲁士哥尼斯堡城的普瑞格尔河上有七座桥连接两岸及河中的两个小岛，当地居民都很喜欢去岛上游玩，但有一个问题困扰着当地居民了很长的时间。在1736年，该市的一位市民向大数学家 欧拉 （Euler）提出了此问题。该问题是，从家里出发，七座桥每座桥都恰好通过一次，然后再回到家里，是否可以办到。事实上，当地居民以前曾反反复复试验了多次，不论怎么样行走，都不能成功的实现每座桥恰好只经过一次，但却没有人严格证明过。
欧拉将两岸分别用B和C两点进行表示，两岛分别用A和D来表示，A、B、C、D各点的位置并不重要，仅当两块陆地之间有桥时，把每座桥用连接对应点的一条边代替，每条边的曲直长短也不重要，于是欧拉将上图的实际场景抽象为下图，并且将此图形称为 图 （graph）。
为了解决这个具体的问题，欧拉提出了判定一般图存在这种走法的充要条件，并给出了必要性证明，开创了图论（ 一维拓扑 ）的研究。这个结果发表于1736年，其把问题归结为一笔画问题，证明了从家里出发，七座桥每座桥都恰好通过一次，然后再回到家里，是不可以办到的。此论文被公认为第一篇图论文章，欧拉本人也被尊崇为图论和拓扑学之父。欧拉在解决此问题的同时给出了连通图可以一笔画的充要条件是：奇点的数目不是0个就是2个（连接到一点的数目如果是奇数条，就称为奇点，如果是偶数条就称为偶点，要想一笔画成必须中间点均是偶点，也就是说来去必须有对应，奇点只可能在两端，因此任何图如果要一笔画成，奇点要么没有要么在两端）
当时的数学界起初并未对欧拉解决七桥问题的意义有足够的认识，甚至有些人仅仅当其为一个数学游戏。图论诞生后并未及时获得足够的发展，直到200年后的1936年，匈牙利数学家科尼希出版了《有限图与无限图理论》，此为图论的第一部专著，其总结了图论200年的成果，是图论发展的第一座里程碑。此后，图论进入发展与突破的阶段，又经过了半个多世纪的发展，现已成长为数学科学的一个独立的重要学科。而且其分支很多，例如图论、算法图论、极值图论、代数图论、随机数图论、模糊图论、超图论等。特别值得一说的是，由于现代科学尤其是大型计算机的迅猛发展，使得图论大有用武之地，无论是数学、物理、化学、地理、生物等基础科学，还是信息、交通、战争、经济乃至社会科学的众多问题，都可以应用图论方法予以解决。当然， 图论也是计算机科学最重要的基础之一 。
注：一笔画
1）凡是由偶点组成的连通图，一定可以一笔画成。画时可以将任意一偶点作为起点，最后一定可以以此点为终点画完此图。
2）凡是只有两个奇点的连通图（其余都为偶点），一定可以一笔画成。画时必须将一个奇点作为起点，而另一个奇点将为终点。
3）其它情况的图都不能一笔画出。 // 奇点数除以二便可以算出此图需要几笔才能画成。
注： 欧拉通过对七桥问题的研究，不仅解决了哥尼斯堡居民提出的问题，而且得到并证明了更为广泛的有关一笔画的三条结论，人们将之称为 欧拉定理 。对于一个连通图，通常把某点出发 一笔画所经过的路线叫 欧拉路 ，同时将一笔画成又回到出发点的欧拉路称为 欧拉回路 ，而具有欧拉回路的图被称为 欧拉图 。
于中阳 Mercina-zy
