一笔画问题

维基百科,自由的百科全书
跳转至: 导航搜索

一笔画问题图论中一个著名的问题。一笔画问题起源于柯尼斯堡七桥问题数学家欧拉在他1736年发表的论文《柯尼斯堡的七桥》中不仅解决了七桥问题,也提出了一笔画定理,顺带解决了一笔画问题[1]。一般认为,欧拉的研究是图论的开端。

与一笔画问题相对应的一个图论问题是哈密顿问题

问题的提出[编辑]

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

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

一笔画定理[编辑]

对于一笔画问题,有两个判断的准则,它们都由欧拉提出并证明[1]

定理一[编辑]

连通的无向图 G 有欧拉路径的充要条件是:G中奇顶点(连接的边数量为奇数的顶点)的数目等于0或者2。

连通的无向图 G 是欧拉(存在欧拉回路)的充要条件是:G中每个顶点的度都是偶数。[2]

证明[2][3]
  • 必要性:如果一个图能一笔画成,那么对每一个顶点,要么路径中“进入”这个点的边数等于“离开”这个点的边数:这时点的偶数。要么两者相差一:这时这个点必然是起点或终点之一。注意到有起点就必然有终点,因此奇顶点的数目要么是0,要么是2。
  • 充分性:
    1. 如果图中没有奇顶点,那么随便选一个点出发,连一个环C_1。如果这个环就是原图,那么结束。如果不是,那么由于原图是连通的,C_1 和原图的其它部分必然有公共顶点 s_1。从这一点出发,在原图的剩余部分中重复上述步骤。由于原图是连通图,经过若干步后,全图被分为一些环。由于两个相连的环就是一个环,原来的图也就是一个欧拉环了。
    2. 如果图中有两个奇顶点 uv,那么加多一条边将它们连上后得到一个无奇顶点的连通图。由上知这个图是一个环,因此去掉新加的边後成为一条路径,起点和终点是 uv。证毕。

连通无向图有欧拉路径的充要条件也可以写作“图中奇顶点数目不多于2个”,这是因为奇顶点数目不可能是1个。实际上,连通无向图中,奇顶点的数目总是偶数。

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

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

定理二[编辑]

如果连通无向图 G2k 个奇顶点,那么它可以用 k 笔画成,并且至少要用 k 笔画成[2]

证明[2][3]
将这 2k 个奇顶点分成 k 对後分别连起,则得到一个无奇顶点的连通图。由上知这个图是一个环,因此去掉新加的边後至多成为 k 条欧拉路径,因此必然可以用 k 笔画成。但是假设全图可以分为 q 条欧拉路径,则由定理一知,每条链中只有不多于两个奇顶点,于是 2q \ge 2k。因此必定要 k 笔画成。

有向图的一笔画[编辑]

对有向图来说,一笔画不仅指遍历所有边,而且要遵循正确的方向。严谨地说,一个连通有向图G有欧拉路径,指存在一个顶点,从它出发,沿着有向边的方向,可以不重复地遍历图中所有的边。有向图的欧拉回路则是指可以从某一顶点开始,沿有向边的方向不重复地遍历所有边,然后回到原来出发的顶点。用类似于定理一中证明的思路,可以得到有向图一笔画的判定准则:

  • 一个连通的有向图可以表示为一条从顶点uv的(不闭合的)欧拉路径的充要条件是:u的出度(从这个顶点发出的有向边的数量)比入度(指向这个顶点的有向边的数量)多1,v的出度比入度少1,而其它顶点的出度和入度都相等。
  • 一个连通的有向图是欧拉环(存在欧拉回路)的充要条件是以下两个之一:
    1. 每个顶点的出度和入度都相等;
    2. 存在一系列的(有向)环C_1, C_2 , \cdots , C_m,使得图G里的每一条边都恰好属于某一个环。

例子[编辑]

图一:无法一笔画
图二:尽管按照中文书写习惯“串”字不止一笔,但它可以一笔写成。

七桥问题[编辑]

右图一是七桥问题抽象化後得到的模型,由四个顶点和七条边组成。注意到四个顶点全是奇顶点,由定理一可知无法一笔画成。

一个可以一笔画的例子[编辑]

图二是中文“串”字抽象化後得到的模型。由于只有最上方和最下方的顶点是奇顶点,由定理一知它可以一笔画成。

一笔画问题与哈密顿问题[编辑]

一笔画问题讨论的是能否不重复地遍历一个图的所有边,至于其中有否顶点的遍历或重复经过则没有要求。哈密顿问题讨论的则是顶点的遍历:能否不重复地遍历一个图的所有顶点?[4]哈密顿问题由哈密顿在1856年首次提出,至今尚未完全解决[2]

参见[编辑]

参考来源[编辑]

  1. ^ 1.0 1.1 1.2 Janet Heine Barnett, Early Writings on Graph Theory: Euler Circuits and The KÄonigsberg Bridge Problem
  2. ^ 2.0 2.1 2.2 2.3 2.4 熊斌,郑仲义,《图论》,第四章,38-46,华东师范大学出版社。
  3. ^ 3.0 3.1 详细的证明
  4. ^ 欧拉图和哈密顿图