淘客熙熙

主题:【原创】上帝之书 -- 我爱莫扎特

共:💬277 🌺1121
全看分页树展 · 主题 跟帖
家园 【原创】我说几句七桥问题吧

既然提到了,我简短的说几句。大家也可以直接看 http://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg 。

这是一个真实的故事,格尼斯堡(Knigsberg)是原普鲁士的一个小城,现在应该在俄国,改名为加里宁格勒(Kaliningrad),城里有条河,河上有七座桥。人们一直很想知道,是不是有一种办法可以把所有桥走一遍,且每个桥只经过一遍。

欧拉第一个解决了这个问题。他的解法开创了一个学科:图论(Graph theory),学计算机的朋友应该很熟悉。

因为解法不难,我很快的解释一下。首先把陆地看成点,把桥看出点点间的连线。

点看全图

外链图片需谨慎,可能会被源头改

=> 点看全图

外链图片需谨慎,可能会被源头改

=> 点看全图

外链图片需谨慎,可能会被源头改

问题相当于说在这些点之间找一条道路,使得每条线都经过且只经过一次。这类问题称为“一笔画”问题。

欧拉给出了一笔画问题的一般解答。

如果我们把每个点连出去的线的数目称为该点的度数(degree)的话。则只有那些度数为奇数的点不超过两个的图才能够被一笔画。

这很好理解。一个一笔画的图,除去它的起点和终点外,中间每个点每次被经过都应该有一条线“进来”,一条线“出去”,因为每条线只用一次,该点的度数一定是偶数。于是只有起点终点可能有奇数的度数。

再看原题,它四个点的度数分别是5,3,3,3。当然无解啦。

不难吧。

关键词(Tags): #数学#勾股定理

本帖一共被 1 帖 引用 (帖内工具实现)
全看分页树展 · 主题 跟帖


有趣有益,互惠互利;开阔视野,博采众长。
虚拟的网络,真实的人。天南地北客,相逢皆朋友

Copyright © cchere 西西河