一笔画问题的不严谨证明
(2018-02-26 14:47:02)
标签:
杂谈数学一笔画 |
分类: 周边 |
原创,如有引用请注明来源
昨夜失眠,忽然想起最强大脑这一季百人筛选的最后一题,也就是立体一笔画问题,又叫七桥问题。记得小时候看过某一版类似《十万个为什么》的书,里面收录了七桥问题,但是限于篇幅仅仅给出了结论和一些讲解,而没有给出证明。在看最强大脑比赛的时候我想起当时看到的结论,并想到了一个思路,于是昨夜顺着这条思路完整地不严谨证明了这个立体一笔画问题。下面先介绍一下什么是七桥问题。
在一座城市有一条河,河中心有两个岛,在河上有七座桥分别连接了河的两岸以及这两个岛。问题是是否能够一笔画的方法把这七座桥都走一遍而没有重复。我们可以把问题变形一下,把岸和岛看成点,桥看成曲线,这样共有四个顶点和七条曲线,问题变成是否能用一笔画的方法画出全部的曲线并且没有重复?再扩展一下,对任意多的顶点和连接线组成的图形,是否能够一笔画?
当时书中给出的结论是先数一数有多少个顶点连接了奇数条连接线,如果这样的顶点数为0或者2,那么这个图像就可以一笔画。也就是说,有奇数条边的顶点数量等于0或2是可以一笔画的充分条件。(其实是充要条件,必要部分与问题无关,不讲解了)
我们先暂时忽略这个结论是否正确,把目光转向另一个问题。七桥一笔画问题是平面的,到立体一笔画问题之间有个二维到三维的鸿沟。在这里我先证明对立体图形也可以使用平面的七桥问题的结论。考虑对任意立体图形,有确定多个顶点,把这些顶点画在一个平面的圆上,这样每个边都连接两个顶点,这样就把立体图形转换成了平面图形,这是一种拓扑方法。这样,只要证明了平面一笔画问题,就可以证明立体一笔画问题。
下一步,来证明有奇数条边的顶点数量等于0或2是平面一笔画的充分条件。首先,大家可能有疑惑为什么有奇数条边的顶点数量不能是1?咱们从最简单的情况来看,一条线段,有两个顶点和一条边,可以一笔画。线段的有奇数条边的顶点数量等于2,两条线段这个数量就等于4,三条就等于6。如果其中有两条线段各自的一个顶点是同一个顶点,也就是线段相连,那么两个相连线段的顶点数量还是2。为什么不可能是1或是奇数呢?因为边是线段,线段总是有两个顶点。如果把所有连接点拆开,那么顶点数一定是线段的2倍,也就是偶数。对于一个有n个边的顶点来说,拆开它所连接的全部线段,那么这个顶点会变成n个新顶点。所以如果有奇数个边的顶点拆开会变成奇数个顶点,如果这种顶点在拆开前是奇数个,那么拆开后还是奇数个。这样与前面说的全部拆开后顶点数量是偶数矛盾。所以有奇数条边的顶点数量一定是偶数。
再进一步,我们来看为什么0和2这样特别。我们来看一个圆,并且在圆上随意取若干个顶点。圆是可以一笔画的,并且有奇数条边的顶点数量是0,因为所有的顶点都有左右两个弧线与旁边的点相连,那么这个0和2有什么区别呢?其实没有区别。还是这个圆,我们把其中任意两个相邻顶点之间的连线抹去,这个圆就有了一个开口。这样,虽然这个新图形仍然可以一笔画,但是最后的一笔没有了,并且产生2个有奇数条边的顶点。另一种情况,如果两个奇数边的顶点之间有连接线,那么考虑把这个连接线去掉后变成没有奇数边顶点的图形,只要一笔画的时候能够保证起点和终点会在同一个顶点,再把这条线加上就能完成一笔画。如此一来有奇数条边的顶点数量是0还是2没有区别,0和2仅仅是这个圆是否开口,不会影响一笔画的结果。这样只要证明了有奇数条边的顶点数量为0的图形可以一笔画就可以了。
到这里基础部分都已经讲解完毕了,想必各位读者已经了解了我的大部分思路,没错我的思路都是来自于这个圆形,并且逐步完善。下面我将继续在这个圆的基础上添加更丰富的内容,来完成补刀,证明有奇数条边的顶点数量为0的图形可以一笔画,并且起点和终点是同一个点。
当一个图形的所有顶点都连接了偶数条边的时候,可以推断,至少有一个顶点,可以在这个图形里不重复地绕回到起点,而先不考虑是否走完全程。对任意一个起点来说,都有偶数个连接线。如果从一个顶点出发不会回到原点的话,那么我们把所有从这条边走到的点标记出来,那么我们从其他边出发都不能连接到刚刚标记的点,也就是说这个图形里分成了两个部分,而且这两个部分在这一个顶点的一条特定的边线连接。如果把图形从这个顶点拆开,两边一定都是有奇数边顶点的图形,而这意味着原图形不是全偶数边顶点。所以,在不考虑走完全程的情况下,全偶数边顶点的图形一定可以从任意一个顶点出发回到这个顶点。
到这里,一笔画的问题基本明了了,我们已经证明了对奇数边顶点数量为0或2的图形,都可以不重复地一笔画,但不保证走完全程。我们的最后一击就是证明这样的图形可以走完全程。
对任意复杂的全偶数边顶点的图形而言,因为至少存在一条从任意顶点出发再回到这个顶点的路线。这条路线经过了相应顶点的偶数条边。把这些边抹去,可能有一些没有边的顶点,它们都已经完成了使命,也一起抹去。剩下的所有顶点仍然有偶数条边,仍然可以从任意点出发再回到出发点。这样重复迭代,一定可以达到完全没有剩余顶点的状态,也就是走完了全程。这一过程也说明全偶数边顶点的图形一定是若干个一笔画路线的组合。
至此全部证明完成。
后一篇:四色问题的不严谨证明