一笔画问题 要图和解释

一笔画问题 要图和解释
一笔画问题 要图和解释

一笔画问题 要图和解释
一笔画问题是图论中一个著名的问题.一笔画问题起源于柯尼斯堡七桥问题.数学家欧拉在他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 详细的证明
^ 欧拉图和哈密顿图

1736年，欧拉在交给彼得堡科学院的《哥尼斯堡7座桥》的论文报告中，阐述了他的解题方法。他的巧解，为后来的数学新分支——拓扑学的建立奠定了基础。 七桥问题和欧拉定理。欧拉通过对七桥问题的研究，不仅圆满地回答了哥尼斯堡居民提出的问题，而且得到并证明了更为广泛的有关一笔画的三条结论，人们通常称之为欧拉定理。对于一个连通图，通常把从某结点出发一笔画成所经过的路线叫做欧拉路。人们又通常把一笔画成回到出...

全部展开

1736年，欧拉在交给彼得堡科学院的《哥尼斯堡7座桥》的论文报告中，阐述了他的解题方法。他的巧解，为后来的数学新分支——拓扑学的建立奠定了基础。 七桥问题和欧拉定理。欧拉通过对七桥问题的研究，不仅圆满地回答了哥尼斯堡居民提出的问题，而且得到并证明了更为广泛的有关一笔画的三条结论，人们通常称之为欧拉定理。对于一个连通图，通常把从某结点出发一笔画成所经过的路线叫做欧拉路。人们又通常把一笔画成回到出发点的欧拉路叫做欧拉回路。具有欧拉回路的图叫做欧拉图。 此题被人教版小学数学第十二册书收录.在95页。 此题也被人教版初中第一册收录．在121页． 一笔划：■⒈凡是由偶点组成的连通图，一定可以一笔画成。画时可以把任一偶点为起点，最后一定能以这个点为终点画完此图。 ■⒉凡是只有两个奇点的连通图（其余都为偶点），一定可以一笔画成。画时必须把一个奇点为起点，另一个奇点终点。 ■⒊其他情况的图都不能一笔画出。(奇点数除以二便可算出此图需几笔画成。)

收起