困扰了我好久好久的问题求大神解答，一线相连24点，不能重合，不能是斜线，空格处不走线！
1个回答
展开全部
想这么久真是难为你了，因为这道题无解。
先重复说一下要求，经过图中所有点一次且仅一次，只能有相邻点连通,不要求回到原点
这是著名的哈密顿路径，其中更复杂的问题是目前还未解决的。
1.理论的证明方法
我们可以找到哈密顿路径存在的一些必要条件。
有定理：如果能够减去N个点使得原图变为多于（大于不能等于）N+1 互不连通的部分（连通分支），则一定不存在哈密顿路径。
因此我们去掉第一行，第二列的点，与所有跟这个点可以通过斜线连接的一共11个点（也即奇数行的偶数列的点与偶数行奇数列的点，此时剩余部分互不连通），
将原图分为了13部分。
2.直观的证明方法，利用国际象棋中的黑白色，把(1,1)点涂为白色，然后使相邻的点异色。
我们可以发现，每次必然从黑点到白点，且黑点数量有13个，白点数量有11个，因此不存在这样的通路。
先重复说一下要求，经过图中所有点一次且仅一次，只能有相邻点连通,不要求回到原点
这是著名的哈密顿路径，其中更复杂的问题是目前还未解决的。
1.理论的证明方法
我们可以找到哈密顿路径存在的一些必要条件。
有定理：如果能够减去N个点使得原图变为多于（大于不能等于）N+1 互不连通的部分（连通分支），则一定不存在哈密顿路径。
因此我们去掉第一行，第二列的点，与所有跟这个点可以通过斜线连接的一共11个点（也即奇数行的偶数列的点与偶数行奇数列的点，此时剩余部分互不连通），
将原图分为了13部分。
2.直观的证明方法，利用国际象棋中的黑白色，把(1,1)点涂为白色，然后使相邻的点异色。
我们可以发现，每次必然从黑点到白点，且黑点数量有13个，白点数量有11个，因此不存在这样的通路。
更多追问追答
追问
悟性不够高，看不懂啊
追答
直接说直观的方法吧，
如果按照国际象棋的方法染色，让相邻的两个格子异色，那么由于连线也只能连相邻的两个格子，连线的两个格子必然是异色的。
我们可以直接数出来，如果把第一行第一列染成白色，那么一共有13个白色跟11个黑色。
显然，无论是从白色还是从黑色开始连，要保持白-黑-白-黑-。。。。。。 黑白的颜色至多只能相差一个，也就是从白色开始到白色结束，而两者相差两个，是不可能连通的
已赞过
已踩过<
评论
收起
你对这个回答的评价是？
推荐律师服务：
若未解决您的问题，请您详细描述您的问题，通过百度律临进行免费专业咨询
