《从“切蛋糕问题”谈到欧拉在图论上的贡献.doc》由会员分享，可在线阅读，更多相关《从“切蛋糕问题”谈到欧拉在图论上的贡献.doc（15页珍藏版）》请在金锄头文库上搜索。
1、北清桥东中培训中心从“切蛋糕问题”谈到欧拉在图论上的贡献从圣诞节到新年之间，我们有几天假期。我们几个老朋友就选择一个晚上，各自准备点吃的东西欢聚在一起。吃吃喝喝完后，大家各出一些需要动脑筋想的问题消遣，于是字谜啦、数学游戏等都出场了。当晚，煮一手好菜的老黎和我都各出一个问题，后来我发现这二个问题都和一门正在蓬勃发展的数学图论（Graph Theory）有关系。于是今天就打算谈谈这二个问题，顺便也介绍一下这门在国内正受到数学工作者注意的数学。切蛋糕问题我先提出这样的一个斗智比赛：现在有一盘蛋糕在面前，给你一把刀子，你要一刀一刀切下去，不可以用手挪动蛋糕，谁能六刀切出最多块的谁就是胜利者。我们的面
2、前有大华姐制成的香喷喷的蛋糕，但是我们并不是真的就拿刀子在上面切割起来，如果是那样大华姐准会气得呱呱叫。而是在一张纸上，画一个差不多像那个可怜的阿Q所画的那个圆，然后画一直线割这个圆代表刀痕。这个问题有很多答案。同一个家庭里的成员就有不同的结果。许太太说只能切出12块，而一向做事细心的老许说他能切出22块！公说公有理、婆说婆有理，你说我这个裁判该听谁的？小鬼小郑喊道：“我切出也是12块！少数服从多数应该是12块。”让我们看看他们的结果吧！很明显的许先生应该是胜利者，你看他只用五刀就已切出16块来，再加上一刀不是更“犀利”？老许说如果你小心的切应该是可以切出22块出来，那么读者请你自己试试看吧！
3、从小郑和许太太的结果，我们可以看出一个这样的事实，如果期望能多切出一些蛋糕，要“规规矩矩”像孔老夫子那样肉割不正不吃的方法是行不通的。不应该有二刀平行割，也不要有三刀都通过同一点的现象出现。那么你就有法子割出较多块了。我这里要提一个问题：现在想像我们的蛋糕是很大，可以一刀一刀的继续切下去，能不能找到一个数学公式来计算每一次后应该有多少块数出现？我们现在就来解决这个问题：我们令f（n）表示n刀下去后出现的蛋糕的块数。从实际经验中，我们知道f（1）=2，f（2）=4。但是f（3）不是6，而是7！大家请看看本文上面列出的三个切法。如果第三刀切时不和任何先前一刀平行，或者通过二刀的交点（数学家可能建议
4、这样讲：三个刀痕的直线不共点），它就能比原先多切出了三块出来。因此，f（3）f（2）3437如果第四刀也是照这样的方法切，它就切出比原先的数目多出4块来，即f（4）f（3）4=74=11如此类推，一般我们有f（n）=f（n-1）n。因此如果能知道前面第n-1刀后的块数，我们就可以算出f（n）了。有没有直接公式表示f（n）呢？以下我们介绍一个巧妙的方法算出这个公式。f（1）=2f（2）f（1）2f（3）=f（2）3 f（n-1）f（n-2）（n-1）f（n）f（n-1）nf（1）f（2）f（n-1）f（n）f（1）f（2）f（3）f（n-1）223（n-1）n在上面的算式中，我们消去二边都出现的
5、数，可以得到f（n）223（n-1）n1（123n）这就是我们的切蛋糕的公式了！你说巧不巧？妙不妙？这个问题可以再推广，而且能用类似以上的方法获得更一般的公式读者有兴趣可以看后面的“动脑筋问题”里的问题。 老黎提的问题 现在让我们回到那新年前的晚会吧！我们的老黎，也是一个数学爱好者，他出的问题就是一般数学上称为：“一笔画问题”。你看他在一张纸上画了一个图，然后要我们大家也一笔画出来。我看了看就对老黎喊道：“喂！老黎！你的图不可能一笔画出来的。你看是不是画错了？”老黎想想就说：“对不起！我的图画错，现在改一改。”结果是一个平日靠画图为生的老章师傅，妙手一挥一笔画出了老黎的第二个图，当然我也画出来
6、。为什么我知道老黎第一次画的图是不能一笔画成的呢？读者如果不相信请你试试看能不能一笔画成，我敢和你赌一万元你画不成。我把老黎的第一个图看成是由点以及线组成的一种集合。在那图里直线的交点就用一个小圆圈表示，我把那图变成这样的图三。这图画的并不像老黎的图那样好看，可是用数学（拓扑学Topology）的观点来看，这二个图是一样的（即同胚homeomorphic）。这个图（graph）的小圈圈就称为顶点（vertex），顶点和顶点的联线就称为边（edge）。这个图是联通的（connected），即任何二个顶点，都有通道连起来。我们现在把图里的顶点分类：一个顶点如果有偶数条边联它，这点就称为偶点；当然相
7、反的有奇数条边联它的就称为奇点。在图三里A点是奇点，因为有三条边通过它。B和C是偶点。这里的图有六个奇点，四个偶点。我知边能一笔画的图只有二类：（1）所有的点都是偶点，（2）只有二个奇点。因此图三不可能一笔画成。这个结果是欧拉最初明确证明，而且是图论的第一个定理。欧拉可以说是“图论”的开山祖师。 哥尼斯堡的七桥问题欧拉（LEuler17071783）是18世纪最杰出的瑞士数学家，他的兴趣非常广泛。在他对数学、天文、物理产生兴趣之前，他是研究神学、东方语文和医学的。他对医药、园艺和化学有过一些研究，而且由于他通晓古代希腊文和拉丁文，他也差不多读遍了能找到手的古代罗马作家的文学作品。奇怪的事。欧拉
8、就由此研究级数理论，建立了可以说是近代数学分析的基础理论。一个卓越的哲学家在对数学作一点研究后，提出这样的看法：“数学，把某个确定的数，例如把一个二项式，化为无穷级数，即化为某种不确定的东西，从常识来说，这是荒谬的举动。但是，如果没有无穷级数和二项式定理，那我们能走多远呢？”他讲的真是对！欧拉在1727年20岁的时候，被俄国请去在圣彼得堡（原列宁格勒）的科学院做研究。差不多在这个时候，他的德国朋友告诉他一个曾经令许多人困惑的问题。，这城现被苏联占领，就像老沙皇把从中国占领的土地改名一样，这城现被改称为卡里林格勒（Kaliningrad）。有一条河横贯市内，河中心有二个小岛。在当时有七座桥把这小
9、岛和对岸联结起来。（见图四）在周末当地的市民喜欢在城里溜达，有人曾想法子从家里出发，走过所有的桥回到家里，他们想是否能有座桥只走过一次。许多人试过都不成功。现在是否有一个方法能走过？欧拉的朋友知道这个青年人很聪明，并且喜欢思考问题，就告诉他这个“哥尼斯堡七桥问题”，要他想法子解决。读者最好先在图四上“纸上漫步”，看看能不能走出一个法子来。如果行不通，那么就继续下去。欧拉并没有跑到哥尼斯堡去走走。他把这个问题化成了这样的问题来看：把二岸和小岛缩成一点，桥化为边，二个顶点有边联结，当且仅当（if and only if）这点代表的地区有桥联结起来。这样欧拉就得到了一个图了。 欧拉如何解决“七桥问题
10、” 欧拉现在考虑这个图是否能一笔画成，如果能够的话，对应的“七桥问题”也就解决了。他先研究一般能一笔画成的图应该具有什么性质？他发现它们大体上有二类，不是全都是偶点就是有二个奇点。这个情形是可以这样的看：如果一个图能一笔画成，那么一定有一个起点开始画，也有一个终点。其他图上的点是“过路点”我们要经过它。现在看“过路点”会有什么性质？它是“能上能下，有进有出”的点，有一条边进这点，那么就要有一条边出去，不可能是有进无出，它就会变成终点，也不可能有出无进，它就会变成起点。因此在“过路点”进出的边总数应该是偶数，即“过路点”是偶点。如果起点和终点是同一点，那么它也是属于“有进有出”的类型，因此必须是
11、偶点，这样图上全体的点是偶点。如果起点和终点是不一样，那么它们必须是奇点了。因此这图最多只能有二个奇点。现在对应七桥问题的图，所有的顶点都是奇点，共有四个，故这个图肯定不能一笔画成。以上说明的方法不完全和欧拉把这个结果在1736年的圣彼得堡科学院学报上发表的一样。我是取其精神，自己改编成较通俗的讲法，希望读者能较容易的明白这个道理。欧拉很喜欢这个结果，他在以后的几个通俗数学演讲，时常以此为话题。我们今天学习欧拉的成果不应是单纯把它当作数学游戏，重要的是应该知道他怎样把一个实际问题抽象化。研究数学问题不应该为“抽象而抽象”，抽象的目的是为了更有效的解决实际产生的问题，欧拉的大作就成为我们学习的一
12、个样板。事实上，中国民间很早就流传这种一笔画的游戏，从长期实践的经验，人们知道如果图的点全部是偶点，可以任意选取一点做起点，一笔画完。如果是有二个奇点，那么就选择一个奇点做起点以顺利的一笔画完。可惜的是古时的一些从事数学研究的儒生，受到“万般皆下品，唯有读书高”的思想毒害，对于民间的游戏当作“下里巴人的雕虫小技”不加以重视。如果那时中国的数学家把这一笔画书的经验总结，以及加以研究，可能“图论”的开山祖师将不是欧拉了。 欧拉在图论上的另一个定理 在平面上有一些点，有一些边把这些点联结了起来，假定这个所得的图是连通的。而一些顶点和边所封闭的区域是一个多边形的样子，我们就称这个图为多边形图（Poly
13、gonal graph）。如底下的图就是多边形图：读者请计算一下这个图有多少个顶点？有多少条边？还有它把平面分成多少块？如果没有算错的话，我们有点数是26，边数是40，块数是16。（读者不要忘记了图外面的那一大块。）现在我们看26-4016=2。这是代表什么意义呢？现在我们令E代表边数，V代表点数，F代表平面被分成的块数，那么我们有V-EF=2这个关系式是欧拉所发现的，在数学上就称为欧拉公式。我们现在看最简单的多边形（图六），这里我们只有一个有n边和n个顶点的多边形，把平面分成里面和外面二块。在这时我们看到V-EF=n-n2=2。现在我们要用数学归纳法来证明这个欧拉公式。假定这个公式对所有具有
14、F块区域的多边形图都是对的。我们要证明对于有F1块区域的多边形图这公式也成立。现在假定平面上有一个多边形图G（图七），我们假定它满足欧拉公式V-EF=2。现在延展这个多边形图到一个新的图，而这时平面的块数是F1。这新图是由原来的图G添上n个新的顶点，以及由n1条边组成的弧把G图的二个顶点联结起来的。现在令新图的点数为V，边数为E和块数为F，则我们有V-EF（Vn）-（En+1）（F1）=2所以由数学归纳法原理，我们知道欧拉公式是恒成立的。 欧拉公式的应用 我们现在利用欧拉公式来解决我们的“切蛋糕问题”，读者可以从这里学习到一点东西，就是：一个数学问题，不仅只有单纯的一个解决方法，一般是有许多种
15、的。应该利用你所具备的知识和条件去尝试解决问题。我们已经知道为了要在切蛋糕时得到更多块数，我们切时，不能有二刀平行切，也不能有三刀经过同一点。现在我们把刀切过蛋糕的边缘的二个点称为边缘点（boundary point），如果我们切n刀，应该有2n个边缘点。因为没有二刀平行切，所以任何二刀切过的直线应该相交在蛋糕内，这样的交点是唯一由这二刀所决定。我们现在切n次，因此这类点共有现在我们要由边缘点及这些蛋糕内刀痕的交点构造一个图出来，我们就称这个图为“蛋糕图”。“蛋糕图”的边在边缘点是这样：相邻的边缘点就由那个蛋糕的边缘的边连起来，其他不相邻的边缘点就没有边连结。而刀痕和刀痕的交点之间的边就由刀痕所决定。请参看图八，这里是n=4的情形。现在让我们开始算蛋糕图里的E和V。蛋糕图的边数E可以这样计算：边缘点有三条边通过它，我们有2n个边缘点，因此在边缘点总共有3（2n）条边通过。任意刀痕的交点个边联。可是我们这样考虑时一条边被计算二次，所以3（2n）+2n（n-1）=2E故E=3n+n2-n=n2+2n现在由欧拉公式V-E+F=2，我们
