中国邮路问题中国邮路问题例题

文章插图
大家好,小豆豆来为大家解答以上的问题。中国邮路问题例题，中国邮路问题这个很多人还不知道,现在让我们一起来看看吧！
1、首先应该说明，这并不能说就是管梅谷教授的“中国邮路问题” 。
2、“中国邮路问题”是欧拉回路的一个变种，可以是各式各样的路线图。
3、也可以是两三个点非常容易的。
【中国邮路问题中国邮路问题例题】4、当然这个也可说是其中之一。
5、你这题目可以证明是无解的。
6、你这样想，既然路线不能重复。
7、图里面又没有相邻的黑点。
8、那每个送信点必须有个独立的入口吧？就是说不可能有两个送信点合用一个入口对吗？那么30个送信点至少要有29个空格（第一个的入口是邮局）。
9、而且一个送信点的入口必须是前一个的出口。
10、就是说出口不能单独占用一个空格，这样29个才够。
11、好，这图上看似正好有29个空格。
12、但是~ 两幢房子旁边的那个空格是没有相邻黑点的。
13、就是说这两个空格不可能作为送信点入口。
14、那么可用作入口的空格只有27个了。
15、显然不够。
16、要说明的是，有29个空格只是必要条件，还并不充分。
17、即使有29个有效空格也不一定就有解。
18、更不用说没有29个了。
19、这个题目理论上应该无解，因为格子总数只有64个，而其中投递点30个格子，依据题目的规定“两个送信地点之间必须要经过一个空白方格，而且不能走对角，而且路线不重复”，需要29个格子，房子3个格子，邮局作为起点和终点，不能用来间隔，占1个格子，左边房子和中间房子的右边相邻的三个格子均为空格，这两个房间右边的空格就不能用于间隔两个投递点了，这里需要浪费掉2个格子，30+29+3+1+2=65 ，大于总的格子数量，因此该题无解。
20、无解。
本文到此分享完毕，希望对大家有所帮助。

中国邮路问题 中国邮路问题例题

中国邮路问题中国邮路问题例题