当前位置: 首页 >> 数学文化 >> 文章正文

哈密尔顿周游世界

哈密尔顿周游世界:1859 年,英国数学家哈密尔顿,发明了一种叫做周游世界的游戏。他用一个正十二面体的二十个顶点代表二十个大城市,要求沿着棱,从一个城市出发,经过所有的城市一次,然后回到出发城市。

用下边的平面图代替正二十面体,也能进行同样的游戏。符合要求的路线很多,也好找。下面这个图中有十六个点,能找到一条路线经过每个点恰好一次吗?这样的路线是不存在的。也就是说,不可能在图中找到一条路线经过每个顶点恰好一次。为什么呢?

这可以用枚举法来给出证明。不过,题目的可能情况太多,用枚举法太繁。那怎么办呢?用反证法。先把这些点涂上红(白)、蓝(黑)两种颜色,使得相邻的两个点颜色
不同。

这样,每走一步,红点只能走到蓝点,蓝点只能走到红点。要是有一条通路存在,那在这条路上,红点与蓝点的个数应当相等。当然也可能相差一个。要是从红点开始,最后一个是蓝点,红点与蓝点一样多;最后一个是红点,红点比蓝点多一个。要是从蓝点开始,这时红点与蓝点个数一样多,或者红点比蓝点少一个。

数一数,图中有七个蓝点,九个红点。它们的差是二。这和红点个数与蓝点个数至多相差为一矛盾。所以,没有一条经过每个点恰好一次的路存在。在数学里,答案为不可能的问题很多。不要认为所有问题的答案都是能。当然,为什么不可能,也同样需要经过严格的证明才能成立。

本文标题:哈密尔顿周游世界

本文地址:http://www.ziyo.org/archives/1746.html

发布:小学数学资优网

发表评论