一语道破一笔画原理

3,246 阅读3分钟

你肯定做过这样的题,问你下面图形能否用一笔画出来,要求不重复不遗漏。

它的一个正确答案是:

而像下面的图形,不妨试试,用一笔且不重不漏,是画不出来的:

估计你也猜测过,图形本身肯定需要满足一些条件才能一笔画出来。

它就是图论中非常有名的:欧拉的一笔画原理。

奇定点的个数要么是0,要么是2,才能一笔画出来!

奇顶点这一概念要说明一下,顶点是与边相连的。连接的边数是奇数的那些顶点称为奇顶点。反之为偶顶点,譬如开篇的图形:

图中共 5 个顶点,其中有 2 个顶点连接边数的个数为奇数(都是3),满足一笔画原理。

此时要画时,需要从其中一个奇顶点画起,最后以另外一个奇顶点结束。比如下图是其他另外一种解法。

只有 0 个奇顶点的情形,比如说一个正方形。显然可以一笔画出来。

或者在上图中再添加一笔后,奇顶点个数也为 0 了。可以试试也能一笔画出来的。此时可以边数较多的点画起,最后还是这个点结束。(其实任意一点都可以)

而下面的图的奇顶点个数有 4 个,因此画不出来。

问题来了,那么为啥奇顶点个数要为 0 或者 2 呢?

这是本文的价值所在,不会去证明,而是要给你一个直观的理解

把一笔画想象成你在走一个迷宫。而迷宫会有入口和出口,因此若要一遍走过所有路径,出入口的个数不能超过两个。要么是 2 个口,要么入口和出口是同一个。只有一个口也就相当于一个封闭的迷宫了。

这个比喻很形象,在画的过程中也容易想到。

用迷宫比喻是很好理解的。假如出入口多于 2 个,比如 3 个吧。

你从一个口进,最后从另一个口出。第 3 个口连接的那条道你必然不会路过,不然,那就有路线重复了。

例如开篇的例子迷宫示意图如下(出入口一定在奇顶点处):

为啥要看奇顶点,而不是偶顶点呢?

非出入口的那些顶点相当于中转站,因为边相当于道路,你从某条道过来,必须得从另一条道出去才行。一进一出、一进一出,因此必须为偶数。

出入迷宫的地方(即出入口)连接的道路倒是可以为奇数,多出的那一条正好可以用来出或者入。

知道原理后,一笔画谜题基本都能解决了。

下面是我录的一笔画游戏的实况录像。过程中基本没卡壳。共 60 关,有点长,每关我都先寻找有奇顶点,从它画起。




另外,说到迷宫,它也是一类常见的题目。可喜的是它有万能解法!

要想快速地走出去,办法就是,在入口处,手扶着墙,然后快速跑,自然而然就会找到出口。其原理就是在图形中找到一个一笔画,比如扶着下面绿色的墙:

扶墙大法好,可以挑战一下下面的迷宫,祝愉快。

希望有所帮助。

本文完。