五分钟让你学会所有笔画(一文弄懂一笔画问题)
【背景】
一笔画问题,最早起源于18世纪时,东普鲁士的首府 —— 哥尼斯堡(也就是现在俄罗斯的加里宁格勒)。在当地,有一条河叫做普雷格河,这条河与它的两条支流,将这座历史名城分为了4个区域。我们通过简化图可以观察到一共有7座桥横跨在河上,其中5座桥连接河中心岛A。
七桥问题
当时的居民便提出这样的一个问题:能否在不重复、只走一遍的前提下,经过所有的桥?许多人都进行了尝试,但终究还是以失败结束。
后来有人找到了欧拉,想请欧拉帮忙解决。在1736年,欧拉通过自己的研究,将其转化为“一笔画问题”,并将自己的研究,总结归纳出“一笔画定理”,从而证实七桥问题的走法根本不存在。
通过此事件,欧拉的研究也开创了数学上的新分支――图论。
【概念解释】
奇点:如果该点处的分支数为奇数,就叫做奇点
偶点:如果该点处的分支数为偶数,就叫做偶点
七桥问题简化图
图中的点A,C,D有三个分支,点B有5个分支,都是奇数,所以它们都是奇点。
【一笔画定理】
一个图形要能一笔画完成必须符合两个条件:
1.图形是连通的;
2.图形中的奇点(与奇数条边相连的点)个数为0或2;
(1)情况一:奇点的个数为0
这时所有的点都是偶点,通过每个点的分支线都是有进有出,并且进出的次数相等。并且发现起笔点也就是停笔点。
图中的每个点都是偶点,我选择从A出发,最后的停笔的点也是点A。
(2)情况二:奇点的个数是2
起笔点与停笔点并不是同一个点,而且必须以一个奇点为起笔点,而另一个奇点就会是停笔点。
图中的点A,B都是奇点,我们可以从A出发试试,看看最后的停笔点是不是B?
【延伸】当奇点数大于2时,是不能一笔画出来的,如果含有2n个奇点的图形,需要n笔画出。
七桥问题
我们前面分析,七桥问题中的四个点都是奇点,所以需要4÷2=2(笔)画出。
【练习】
练习1
练习2
练习3
练习4
,免责声明:本文仅代表文章作者的个人观点,与本站无关。其原创性、真实性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容文字的真实性、完整性和原创性本站不作任何保证或承诺,请读者仅作参考,并自行核实相关内容。文章投诉邮箱:anhduc.ph@yahoo.com