一笔画问题是我的最爱,小学时候我可喜欢一笔画问题了,而且经常拿一笔画问题去考周围小伙伴,每次都会给他们问迷糊了,看着他们答不上来,我的心里美滋滋的。
————Shy
昨天我写了篇图论入门的文章,给两个智商普通的小伙伴看,她俩竟然看懂了,而且觉得很好玩!所以,我决定开始写图论系列的文章。
每一门科学都有发展的起源,图论发展的起源最早可以追溯到一笔画问题,它是图论问题里的最闪耀明星!
- 一座城池
柯尼斯堡,网上也有叫哥尼斯堡的,作为一个中国人,每次国外的名字经常被翻译成好几个版本,令我很纠结。所以这里我不打算用中文叫它了,这座城市德语是——Königsberg。
1255年条顿骑士团北方十字军建立了 Königsberg 这座城市,之后的数百年期间先后被条顿骑士团国(1255年)、普鲁士公国(1525年)和东普鲁士(1641年)定为首都或首府。Königsberg 曾是德国文化中心之一(1932年),伊曼努尔·康德、E·T·A·霍夫曼和达维德·希耳伯特都曾在此居住过。
第一次世界大战德意志国防军将其作为第一军区司令部所在地,最初有成千上万的犹太人在这个城市居住过,世界大战期间,犹太人遭受迫害,人数越来越少最后少于五百人,到了1942年,犹太人开始被遣送至灭绝营。1944年,第二次世界大战,盟军轰炸Königsberg,城市遭受重创,大火燃烧了几天几夜。4月9日,在红军的强烈攻势下,Königsberg 德军司令奥托·拉施率残余部队投降。此时,城市中的军民死亡已达42,000人,大约有12万人幸存,其中大部分是妇女、儿童和老人,而被俘的则超过90,000人。留下来的德国人中,大部分在1949年前死于疾病、刑讯和饥饿。1949年-1950年,最后幸存的2万德国人被陆续驱赶出Königsberg。1945年,根据《波茨坦协定》,Königsberg划归苏联,现在是俄罗斯加里宁格勒州首府。
Königsberg这座城市演绎了和平与战争的交替,它也孕育了伟大的文明,这座城池便是图论的起源地。
- Königsberg七桥问题
Königsberg七桥问题是世界著名古典数学问题之一。
18世纪,在Königsberg的一个公园里,有七座桥将普雷格尔河中两个岛及岛与河岸连接起来,有人提出了一个问题,是否可能从这四块陆地中任一块出发,恰好通过每座桥一次,并且最后回到起点。
当地的居民每周六都会举行活动,看谁能一次走过七座桥。有趣的是没有居民能完成这个目标,要不就是少走一座桥,要不就是某座桥需要经过两次,或者无法回到出发点。到底存不存在一条这样完美的线路——每座桥只能经过一次而且起点与终点必须是同一地点,大家谁也不知道,也无法证明不存在。
- 传说哥
欧拉是画画界里面数学成绩最好的,也是数学界里画画成绩最好的。
1736年,牛逼哄哄的大数学家欧拉造访了Konigsberg这座城市, 他发现了当地居民这个有趣的消遣活动。
如何找出这样一个行走路线,欧拉指出陆地是不重要的,重要的是跨过桥的线路。因为陆地没有任何限制,人们可以不停地走动,只要不经过桥,那么就相当于什么也没做。因为在陆地上任意一点出发,只要不经过桥,不论怎么走都可以回到这个出发点,我们完全可以将陆地看成一个点。所以欧拉把这个问题简化了,他把公园不相连的四块地画成A、B、C、D四个点,而把七座桥画成七条线,每一座桥就是从一个点(陆地)到另一个点(陆地),如图所示。
图的简化过程很清晰,可以看出A陆地和B陆地有两座桥相连所以A点和B点连接两条线,同理B点和D点连接两条线,AC、BC、DC各连一条线,总共七座桥对应七条线。
那么这道问题就变成了,从A、B、C、D任意一点出发,是否可以一笔画出该图形,且每一条线只许画一次,不许重复画,俗称一笔画问题。
神奇不!!!这就是图论的起源,欧拉将复杂的、有公园视觉效果的问题归结成点和线!
- 自由的变换
我说过,做相同图论的问题,有时候图可能画的不一样,这是为什么呢?因为图论的精髓在于画这个动作,而画成什么样不重要,一条线,你画的急了拐弯也好,沟沟八翘也行,直线也罢,都不影响图论的本质。就像下面这两个图,虽然长得不太一样,但其实都是Königsberg七桥问题。
图论解题过程中,你的图画美观可能别人会夸你,你画的埋了乎汰的,别人可能不愿瞅你答案。但是我觉得,画自己的图,让别人喷去吧!我将下面这句名言送给那些画画不好看的人,也包括我自己:
图论解题中,画自己能看得懂的图就是好图,与好看无关。
- 简单到底
回归正题,欧拉证明的思路非常简单。他观察到,除了起始点以外,每经过一个顶点,都是一条线的结束,另一条线的开始。
就是说,每经过一点时,就需要两条线,一条线结束,一条线开始。所以,如果一个点不是起始点,那么这个点的连线必须是偶数,才能保证进入、经过并离开此点。若一个点有奇数条线相连,那么之个点要么是起点,要么是终点。
定义:
奇点 ———— 一个点有奇数条连线。
偶点 ———— 一个点有偶数条连线。
欧拉创造了伟大的欧拉定理:
1. 凡是由偶点组成的连通图,一定可以一笔画成。画时可以把任一偶点为起点,最后一定能以这个点为终点画完此图。
2. 凡是只有两个奇点的连通图(其余都为偶点),一定可以一笔画成。画时必须把一个奇点为起点,另一个奇点为终点。
3. 其他情况的图都不能一笔画出。(奇点数除以二便可算出此图需几笔画成。)
这里简单解释下什么是连通图,就是图里所有点都是可以经过线路互相到达的。比如,这个就是不连通的图,不连通的图画吐血了也不可能一笔画完:
- 轻松证明
如图所示,四个点的连线数分别是3、5、3、3,4个都是奇点,所以不能一笔画成,因此Königsberg七桥问题不存在解。
怎么样,好玩不,是不是很神奇,还不去找智商低的人炫耀去!
Leave a Reply