作者:佚名
| 发表日期:2007-10-31
| 浏览:72次
| 加入收藏
邮递员为了递送邮件,每天要走遍自己投递范围的大街小巷,也就是说,每天,他都要到相同的地方送信,每天都可以走相同的路线,这其中必有一条最短的路线,如果能找到这条路,每天都按着这条路线走,必然可以减少工作量,提高效率。
显然,这个邮递员从邮局出发,走遍每条大街小巷,而且只走过一次,最后回到邮局,这是最短的路线。
有人会说,找到这条路不就完了吗?但事实上,这条路并不一定能找到。那么,在什么条件下,能找到这样最短路线呢?用数学上的一笔画问题可以解决这个难题。所谓一笔画问题,指的是:什么样的图形可以一笔画成,笔不离开纸,而且每条线只画一次不重复。很容易看出,邮递员问题就是一个一笔画问题。
数学家欧拉提出并解决了一笔画问题。一笔画是有一个起点和一个终点的图形,而中间每经过一点都应和偶数条线相连。欧拉把与偶数条线相连的点称为偶点,与奇数条线相连的点称为奇点。如果这个图形是封闭的,那么起点(也就是终点)一定是偶点。而不论什么时候,中间点都是偶点。
除此以外,一笔画图形还必须是由具有两个相异端点的有限条线组成的一个图形(称为网络),任意两个顶点都可用一条线连接,这样的网络称为连通网络。例如,形如“品”字形的网络就不是连通的,它无法一笔画成。
这们,欧拉得到了一个结论:一个网络能够一笔画成,必须是连通的,并且奇点个数是0或2。这就是著名的欧拉定理。有了欧拉定理,邮递路线问题就可以解决了。