主题:【原创】上帝之书 -- 我爱莫扎特
既然提到了,我简短的说几句。大家也可以直接看 http://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg 。
这是一个真实的故事,格尼斯堡(Knigsberg)是原普鲁士的一个小城,现在应该在俄国,改名为加里宁格勒(Kaliningrad),城里有条河,河上有七座桥。人们一直很想知道,是不是有一种办法可以把所有桥走一遍,且每个桥只经过一遍。
欧拉第一个解决了这个问题。他的解法开创了一个学科:图论(Graph theory),学计算机的朋友应该很熟悉。
因为解法不难,我很快的解释一下。首先把陆地看成点,把桥看出点点间的连线。
=>
=>
问题相当于说在这些点之间找一条道路,使得每条线都经过且只经过一次。这类问题称为“一笔画”问题。
欧拉给出了一笔画问题的一般解答。
如果我们把每个点连出去的线的数目称为该点的度数(degree)的话。则只有那些度数为奇数的点不超过两个的图才能够被一笔画。
这很好理解。一个一笔画的图,除去它的起点和终点外,中间每个点每次被经过都应该有一条线“进来”,一条线“出去”,因为每条线只用一次,该点的度数一定是偶数。于是只有起点终点可能有奇数的度数。
再看原题,它四个点的度数分别是5,3,3,3。当然无解啦。
不难吧。
本帖一共被 1 帖 引用 (帖内工具实现)
- 相关回复 上下关系8
🙂说到高产,柯西也是很了不起 1 moudy 字70 2009-03-12 20:35:56
🙂柯西排名第三 我爱莫扎特 字24 2009-03-13 01:01:17
🙂不禁想起欧拉解决的七桥问题。谢谢! 1 lean 字0 2009-03-02 00:50:55
🙂【原创】我说几句七桥问题吧
🙂送花并提个小建议,卡利宁格勒应该是“加里宁格勒”吧? 1 史文恭 字0 2009-03-14 10:47:17
🙂谢教头指正 我爱莫扎特 字8 2009-03-15 14:15:18
🙂F=GMm/r2算一个吗? 2 wxmang的书童甲 字32 2009-02-25 03:57:00
🙂真的很美 1 我爱莫扎特 字143 2009-02-26 17:26:11