点阵连线问题(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的全部解(对称的可以不计在内)或者部份解...