查看“︁一笔画问题”︁的源代码

''' 一笔画问题（Eulerian graph）'''是[[图论]]中一个著名的问题。一笔画问题起源于[[柯尼斯堡七桥问题]]。[[数学家]][[欧拉]]在他1736年发表的论文《柯尼斯堡的七桥》中不仅解决了七桥问题，也提出了'''一笔画定理'''，顺带解决了一笔画问题<ref name="early">Janet Heine Barnett, [http://www.cs.berkeley.edu/~christos/classics/euler.pdf ''Early Writings on Graph Theory: Euler Circuits and The Königsberg Bridge Problem''] {{Wayback|url=http://www.cs.berkeley.edu/~christos/classics/euler.pdf |date=20111218160215 }}</ref>。一般认为，欧拉的研究是[[图论]]的开端。

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

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

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

一笔画问题的推广是多笔画问题，即对于不能一笔画的图，探讨最少能用多少笔来画成。

== 一笔画定理 ==
对于一笔画问题，有两个判断的准则，它们都由欧拉提出并证明<ref name="early"/>。

=== 定理一 ===
连通的无向图 <math>G</math> 有欧拉路径的充要条件是：<math>G</math>中奇顶点（连接的边数量为奇数的顶点）的数目等于0或者2。

连通的无向图 <math>G</math> 是欧拉[[图|环]]（存在欧拉回路）的充要条件是：<math>G</math>中每个顶点的度都是偶数。<ref name="book">熊斌，郑仲义，《图论》，第四章，38-46，华东师范大学出版社。</ref>。
<div style="margin-left:20px; margin-top:10px;padding-left:16px;padding-bottom:10px;padding-right:16px;padding-top:10px;background-color:#E8FFC4;width:90%;">
<div style="font-size:108%;">'''证明'''：<ref name="book"/><ref name="detail">[http://dep.yctc.edu.cn/maths/wlkc/lssx/UploadFile/2008622173748669.pdf 详细的证明]{{dead link|date=2017年11月 |bot=InternetArchiveBot |fix-attempted=yes }}</ref>
</div>
<div style="margin-left:6px;margin-top:6px;font-size:90%;">
* 必要性：如果一个图能一笔画成，那么对每一个[[顶点 (图论)|顶点]]，要么路径中“进入”这个点的边数等于“离开”这个点的边数：这时点的[[度]]为[[偶数]]。要么两者相差一：这时这个点必然是起点或终点之一。注意到有起点就必然有终点，因此奇顶点的数目要么是0，要么是2。
* 充分性：
*# 如果图中没有奇顶点，那么随便选一个点出发，连一个环<math>C_1</math>。如果这个环就是原图，那么结束。如果不是，那么由于原图是连通的，<math>C_1</math> 和原图的其它部分必然有公共顶点 <math>s_1</math>。从这一点出发，在原图的剩余部分中重复上述步骤。由于原图是连通图，经过若干步后，全图被分为一些环。由于两个相连的环就是一个环，原来的图也就是一个欧拉环了。
*# 如果图中有两个奇顶点 <math>u</math> 和 <math>v</math>，那么加多一条边将它们连上后得到一个无奇顶点的连通图。由上知这个图是一个环，因此去掉新加的边後成为一条路径，起点和终点是 <math>u</math> 和 <math>v</math>。证毕。
</div>
</div>
连通无向图有欧拉路径的充要条件也可以写作“图中奇顶点数目不多于2个”，这是因为奇顶点数目不可能是1个。实际上，连通无向图中，奇顶点的数目总是偶数。

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

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

=== 定理二 ===
如果连通无向图 <math>G</math> 有 <math>2k</math> 个奇顶点，那么它可以用 <math>k</math> 笔画成，并且至少要用 <math>k</math> 笔画成<ref name="book"/>。

<div style="margin-left:20px; margin-top:10px;padding-left:16px;padding-bottom:10px;padding-right:16px;padding-top:10px;background-color:#E8FFC4;width:90%;">
<div style="font-size:108%;">'''证明'''：<ref name="book"/><ref name="detail"/>
</div>
<div style="margin-left:6px;margin-top:6px;font-size:90%;">将这 <math>2k</math> 个奇顶点分成 <math>k</math> 对後分别连起，则得到一个无奇顶点的连通图。由上知这个图是一个环，因此去掉新加的边後至多成为 <math>k</math> 条欧拉路径，因此必然可以用 <math>k</math> 笔画成。但是假设全图可以分为 <math>q</math> 条欧拉路径，则由定理一知，每条链中只有不多于两个奇顶点，于是 <math>2q \ge 2k</math>。因此必定要 <math>k</math> 笔画成。
</div>
</div>
===有向图的一笔画===

对有向图来说，一笔画不仅指遍历所有边，而且要遵循正确的方向。严谨地说，一个连通有向图<math>G</math>有欧拉路径，指存在一个顶点，从它出发，沿着[[有向边]]的方向，可以不重复地遍历图中所有的边。有向图的欧拉回路则是指可以从某一顶点开始，沿[[有向边]]的方向不重复地遍历所有边，然后回到原来出发的顶点。用类似于定理一中证明的思路，可以得到有向图一笔画的判定准则：
*一个连通的有向图可以表示为一条从顶点<math>u</math>到<math>v</math>的（不闭合的）欧拉路径的充要条件是：<math>u</math>的出度（从这个顶点发出的[[有向边]]的数量）比入度（指向这个顶点的有向边的数量）多1，<math>v</math>的出度比入度少1，而其它顶点的出度和入度都相等。
*一个连通的有向图是欧拉环（存在欧拉回路）的充要条件是以下两个之一：
*#每个顶点的出度和入度都相等；
*#存在一系列的（有向）环<math>C_1, C_2 , \cdots , C_m</math>，使得图<math>G</math>里的每一条边都恰好属于某一个环。

==例子==
<gallery>
File:Königsberg_graph.svg|图一：无法一笔画，原因：有四个奇顶点，不符合0個或2個奇顶点的條件
File:Chuan2.JPG|图二：尽管按照中文书写习惯“串”字不止一笔，但它可以一笔写成，因為只有上下兩個奇顶点。
File:Hexagram without lifting pen.svg|圖三：[[六角星]]，0個奇顶点
File:Latex voorbeeld tikz.png|圖四，只有兩個在下方的奇顶点
File:Blender3D HouseOfStNiclas.gif|圖五（圖四的動態版）
</gallery><!-- 原本的格式
[[File:Königsberg_graph.svg|right|thumb|150px|图一：无法一笔画]]
[[File:Chuan2.JPG|thumb|150px|图二：尽管按照中文书写习惯“串”字不止一笔，但它可以一笔写成。]]
[[Image:Hexagram without lifting pen.svg|thumb|150px|圖三：[[六角星]]]]
[[File:Latex voorbeeld tikz.png|thumb|150px|圖四]]
[[File:Blender3D HouseOfStNiclas.gif|thumb|150px|圖五 (圖四的圖的動態版)]]-->
===七桥问题===
图一是[[七桥问题]]抽象化後得到的模型，由四个顶点和七条边组成。由於四个顶点全是奇顶点，由定理一（奇顶点的數目正好是0個或2個）可知无法一笔画成。

===一些可以一笔画的例子===

图二是中文“串”字。由于只有最上方和最下方的顶点是奇顶点，由定理一知它可以一笔寫成，圖片內給出了一個例子。

圖三的六角星因每個頂點都是偶頂點，如上，由定理一得知，不論是由哪個點出發，它都可以一筆畫成。

圖四（和圖五）的圖只有最左下方和最右下方的頂點是奇頂點，由定理一知它可以一筆畫成，由其中一個奇頂點畫到另一個奇頂點。

== 一笔画问题与[[哈密顿问题]] ==
一笔画问题讨论的是能否不重复地遍历一个图的所有边，至于其中有否顶点的遍历或重复经过则没有要求。哈密顿问题讨论的则是顶点的遍历：能否不重复地遍历一个图的所有顶点？<ref>{{Cite web |url=http://mathserver.sdu.edu.cn/html/sxjm/texts/chapter5/5_6_1.htm |title=欧拉图和哈密顿图 |accessdate=2008-09-18 |archive-date=2008-09-23 |archive-url=https://web.archive.org/web/20080923134241/http://mathserver.sdu.edu.cn/html/sxjm/texts/chapter5/5_6_1.htm |dead-url=no }}</ref>哈密顿问题由[[威廉·卢云·哈密顿|哈密顿]]在1856年首次提出，至今尚未完全解决<ref name="book"/>。

== 参见 ==
* [[柯尼斯堡七桥问题]]
* [[漢彌爾頓路徑問題|哈密尔顿问题]]
* [[树 (圖論)]]
* [[中国邮递员问题]]

== 参考来源 ==
{{reflist}}

[[Category:图论]]
[[Category:数学问题]]
[[Category:莱昂哈德·欧拉]]