一笔画问题

来自计算思维百科
跳转至: 导航搜索
一笔画问题1.png

一笔画问题是图论中一个著名的问题,要求遍历图总所有路径且没有重复地回到原点。

基本概念

一笔画问题起源于柯尼斯堡七桥问题。在柯尼斯堡问题中,如果将桥所连接的地区视为点,将每座桥视为一条边,那么问题将变成:对于一个有着四个顶点和七条边的连通图,能否找到一个恰好包含了所有边,并且没有重复的路径。

欧拉将这个问题推广为:对于一个给定的连通图,怎样判断是否存在着一个恰好包含了所有边,并且没有重复的路径?这就是一笔画问题。

可以体现的计算思维

一笔画问题常常需要转化为欧拉路径的问题来解决,转化为欧拉路径需要我们把问题抽象成图,从而进行操作,体现了计算思维中的抽象思想。

解决方案

一笔画问题可以转化为查找图中是否存在欧拉路径的问题。

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

对于有向图来说,一笔画不仅指遍历所有边,而且要遵循正确的方向。一个连通的有向图可以表示为从顶点u到v的欧拉路径的充要条件是u的出度(从这个顶点发出的有向边的数量)比入度(指向这个顶点的有向边的数量)多1,v的出度比入度少1,而其他顶点的出度和入度都相等

柯尼斯堡七桥问题

一笔画问题2.png

由于柯尼斯堡七桥问题中存在4个奇顶点(连接的边的数量为奇数的顶点),奇顶点的数目不等于0或者2,因此它不可以一笔画成。

一笔画问题的例子

一笔画问题3.png

我们可以把中文字“串”字抽象为一个无向图,由于只有最上方的顶点和最下方的顶点是奇顶点,由定理一得该图可以一笔画成。在此,还要指出的是一笔画问题讨论的是能否不重复地遍历一个图的所有边,至于其中有否顶点的遍历或重复经过则没有要求。