点阵连线问题(NP)
本帖最后由 数学星空 于 2009-6-23 08:27 编辑将3*3的点阵用4条首尾相连的折线全部串联起来?
将4*4的点阵用6条首尾相连的折线全部串联起来?
将5*5的点阵用8条首尾相连的折线全部串联起来?
将6*6的点阵用10条首尾相连的折线全部串联起来?
......
证明或否定可以将N*N的点阵用2*(N-1)条首尾相连的折线全部串联起来?
注:我们可以称N*N=N^2个点为格点,要求
(1)每个点只能在一条直线上或者为为两条直线交点.
(2)所有直线必须通过所有格点
(3)所有直线是首尾相连,但两端不封闭
(4)允许增加必要的点(可以称为辅助点) 现将部份结果上传,供爱好者分享与讨论,望能给予很好的解决
显然,N=3,4,6结果已经完成,可以肯定结果不唯一
可以先讨论N=5,7,8,9,10....的情形
有兴趣可以将全部解的个数用编程的方法找出来 将3*3的点阵用4条首尾相连的折线全部串联起来?
将4*4的点阵用6条首尾相连的折线全部串联起来?
将5*5的点阵用8条首尾相连的折线全部串联起来?
将6*6的点阵用10条首尾相连的折线全部串联起来?
......
证明或否定可 ...
数学星空 发表于 2009-6-23 08:19 http://bbs.emath.ac.cn/images/common/back.gif
关键是2(N-1)是不是条数最少的呢？我感觉不需要那么多。 现将部份结果上传,供爱好者分享与讨论,望能给予很好的解决
1015
1016
显然,N=3,4,6结果已经完成,可以肯定结果不唯一
可以先讨论N=5,7,8,9,10....的情形
有兴趣可以将全部解的个数用编程的方法找出来
数学星空 发表于 2009-6-23 08:26 http://bbs.emath.ac.cn/images/common/back.gif
图形很漂亮，但是其中6X6的我怎么觉得不满足首尾相连的要求？ 看第一张图的第二个图,就是6*6的结果..
但最少是多少呢,你能画图举例说明吗? 看第一张图的第二个图,就是6*6的结果..
但最少是多少呢,你能画图举例说明吗?
数学星空 发表于 2009-6-23 09:38 http://bbs.emath.ac.cn/images/common/back.gif
我只会3X3的O(∩_∩)O~
感觉这个问题很难，可能跟植树问题差不多，mathe应该可以编出求解的程序。 这个有意思，但找不到思路
显然n=2不存在，我怀疑n>=7也不存在 是啊,这个问题5年前,我曾请教过武大的一个博导,他说这是一个NP问题,并建议构造0,1序列来解决此问题...
可惜还是没有头绪.. 这个编程还是相对比较容易一些.不过显然点数太多时计算机也很难解决 请mathe先用编程的方法搜索N=3,4,5,6,7,8,9,10的全部解(对称的可以不计在内)或者部份解...