点阵连线问题(NP)

数学星空

将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....的情形
     有兴趣可以将全部解的个数用编程的方法找出来

winxos

将3*3的点阵用4条首尾相连的折线全部串联起来?
将4*4的点阵用6条首尾相连的折线全部串联起来?
将5*5的点阵用8条首尾相连的折线全部串联起来?
将6*6的点阵用10条首尾相连的折线全部串联起来?
......
证明或否定可 ...
数学星空 发表于 2009-6-23 08:19

关键是2(N-1)是不是条数最少的呢？我感觉不需要那么多。

winxos

现将部份结果上传,供爱好者分享与讨论,望能给予很好的解决
1015
1016
显然,N=3,4,6结果已经完成,可以肯定结果不唯一
     可以先讨论N=5,7,8,9,10....的情形
     有兴趣可以将全部解的个数用编程的方法找出来
数学星空 发表于 2009-6-23 08:26

图形很漂亮，但是其中6X6的我怎么觉得不满足首尾相连的要求？

数学星空

看第一张图的第二个图,就是6*6的结果..
但最少是多少呢,你能画图举例说明吗?

winxos

看第一张图的第二个图,就是6*6的结果..
但最少是多少呢,你能画图举例说明吗?
数学星空 发表于 2009-6-23 09:38

我只会3X3的O(∩_∩)O~
感觉这个问题很难，可能跟植树问题差不多，mathe应该可以编出求解的程序。

shshsh_0510

这个有意思，但找不到思路
显然n=2不存在，我怀疑n>=7也不存在

数学星空

是啊,这个问题5年前,我曾请教过武大的一个博导,他说这是一个NP问题,并建议构造0,1序列来解决此问题...
可惜还是没有头绪..

mathe

这个编程还是相对比较容易一些.不过显然点数太多时计算机也很难解决

数学星空

请mathe先用编程的方法搜索N=3,4,5,6,7,8,9,10的全部解(对称的可以不计在内)或者部份解...