2018-02-10

寒假打卡第一天

梁学霸的活动，打卡第一天交作业：

今天读了《1089》前三章，重点重新梳理和学习了konisberg bridge problem（这个问题也称为一笔画问题）。

（1）这个问题是17世纪瑞士数学家Leonhard Euler使用reductio ad absurdum 来证明的。

（2）基本概念理清：

1.度数：从一个点出发的线的条数；

2.偶点：度数为偶数的点；

3.奇点：度数为奇数的点；

4.欧拉半回路：经过图中每条线一次且仅一次，不要求一定回到出发点的路；

5.欧拉回路：从图中任意点出发，经过图中每条线一次且仅一次，再回到原来出发点的路线。

6.欧拉回路是欧拉半回路的特例。

（3）欧拉定理：

1.如果奇点的个数为0，则存在欧拉回路。而且可以从任意一点出发。（起点即为终点）

2.如果奇点的个数为2，则存在欧拉半回路（不存在欧拉回路），这个半回路一定是从一个奇点出发，最后到达另一个奇点。

3.如果奇点的个数大于2，则不存在欧拉回路和半回路。也就是无法完成一笔画。

补充：由偶数个奇点除以二便可算出此图需要几笔画成。

（4）证明过程：假设有可能走过每一座桥，而且每座桥只经过一次。即从ABCD其中的一个区域出发，最后回到它们当中的一个（有可能两者都是同一个区域），而途中要通过每一座桥正好一次。

      紧接着就可推断出，至少有两个区域即非这趟步行的起点，也不是终点。针对一个非起点也非终点的区域，我们到达那里几次，就会从那里离开几次，而且因为每一座桥只能走过一次，所以，必定要有偶数座桥连接该区域。

      但是，在这个图示中，没有一个区域有这样的特性，岛A由5座桥连接，岛BCD都是由3座桥连接。所以，证明无法走过这7座桥中的每一座，一次且仅一次。

（4）悟：看起来很简单的问题，实际上可能更复杂。但是，当感觉很复杂困难的时候，可能有简单有效的方法立马就解决了。