首页 理论教育 “一笔画问题”

“一笔画问题”

时间:2023-02-13 理论教育 版权反馈
【摘要】:虽然图形各式各样,但能够一笔画成的图形却只有两种情况:我们来看第一种情况,图形是连通的,而且没有奇点,如图2。于是可以把这个图形一笔画出,并且第一笔画的可以就是添上去的那条虚线。再把第一笔去掉,就把原来的图形一笔画出了:A4、A2、A1、A6、A5、A4、A3、A2、A6。

“一笔画问题”

有这样一个迷宫,只有A1一个出口,里面是全封闭的。

你能从A1点出发不重复地走过所有通道,再从A1点出来吗?这实际上是一个古老的数学游戏——“一笔画”问题,即由某些点和线段所组成的各种图形,能不能不重复地由一笔画成。

img469

什么样的图形可以一笔画成?这些图形有没有什么规律呢?下面我们来看一个图形(如图1),图中任意两点都可以用若干线段把它们连接起来,这样的图形称为是“连通”的。图中的点可分为两类:凡是从这个点出发的线段的数目是奇数的,称为奇点(如A、B点);凡是偶数的,就称为偶点(如C、D、E、F、G、H点)。虽然图形各式各样,但能够一笔画成的图形却只有两种情况:

1.图形中所有的点都是偶点,就可以从图形的任意一点出发一笔画成;

img470

图1

img471

图2

2.图形中只有两个奇点,可从其中一个奇点出发一笔画成。

为什么这两种图形可以一笔画成呢?

img472

图3

img473

图4

我们来看第一种情况,图形是连通的,而且没有奇点,如图2。从图上任意一点出发,可以划一条闭回路,如从A1出发,经A2、A5、A6最后回到A1(即图上虚线划出的部分)。现在将这一部分擦去,留下的部分如图3,这个图形仍旧只有偶点。同样可以像上面一样找到一条闭回路,如A6、A7、A3、A6。又因为A6这一点在上一条闭回路中也有,因此,可以将后面的闭回路接到前面的闭回路上去,得到这样一条更大的闭回路:A1、A2、A5、A6、A7、A3、A6、A1。下面把这一条闭回路也擦去,再在留下的部分中找闭回路,再接到上面的闭回路中去。这样下去,可以把整个图形连接成一条闭回路,也就是说把整个图形一笔画成。

现在就能很容易地说明第二种情况了。在图4中,只有A4、A6两个点是奇点,其余都是偶点。我们只要在两个奇点之间添一条线,它们也都变成了偶点,这就成了第一种情况了。于是可以把这个图形一笔画出,并且第一笔画的可以就是添上去的那条虚线。如A6、A4、A2、A1、A6、A5、A4、A3、A2、A6。再把第一笔去掉,就把原来的图形一笔画出了:A4、A2、A1、A6、A5、A4、A3、A2、A6

到这里,我们可以很容易地解决开头的迷宫问题了。因为里面走道所形成的图形是连通的,而且交叉点全是偶点,所以要不重复地走过所有走道,再回到出发点是可能的。其中一种走法是:A1、B2、B1、C1、C2、D2、D1、E1、E2、F1、F2、E3、E2、D2、D3、C3、C2、B3、B3、C3、C4、D4、D3、E3、E4、F3、F3、E5、E4、D4、D5、D6、E6、E5、D5、C5、C4、B4、B5、B6、C6、C5、B5、A4、A3、B4、B3、A2、A1

其实,还有很多种走法,你不妨试一试。

免责声明:以上内容源自网络,版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。

我要反馈