“一笔画问题”

“一笔画问题”

有这样一个迷宫，只有A₁一个出口，里面是全封闭的。

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

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

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

图1

图2

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

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

图3

图4

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

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

到这里，我们可以很容易地解决开头的迷宫问题了。因为里面走道所形成的图形是连通的，而且交叉点全是偶点，所以要不重复地走过所有走道，再回到出发点是可能的。其中一种走法是:A₁、B₂、B₁、C₁、C₂、D₂、D₁、E₁、E₂、F₁、F₂、E₃、E₂、D₂、D₃、C₃、C₂、B₃、B₃、C₃、C₄、D₄、D₃、E₃、E₄、F₃、F₃、E₅、E₄、D₄、D₅、D₆、E₆、E₅、D₅、C₅、C₄、B₄、B₅、B₆、C₆、C₅、B₅、A₄、A₃、B₄、B₃、A₂、A₁。

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