论坛 › 趣题妙解 › 一个著名题目——等距排布问题

mathe 发表于 2025-4-25 14:23:25

试了一下n=8中的文件
ABAEAFBGBHCDCECGDFDHEFEGFHGH.sg.8
对应的解含有一个变参，所有对应的是一系列图

可以通过geogebra制作出动图

mathe 发表于 2025-4-25 19:51:40

n=12也应该是动图，含有一个参数，方程为
ii=v(22)
ii=3*v(21)+(-w)*v(22)-3
ii=2*v(20)+(-w)
ii=2*v(19)-1
ii=2*v(18)+(-w)*v(19)+v(20)-2*v(22)+(w)*v(23)-v(24)
ii=3*v(17)+(w)*v(18)+(2*w)*v(20)-3*v(21)+(-w)*v(22)+(-2*w)*v(24)
ii=v(16)
ii=v(15)-1
ii=2*v(14)+(-w)*v(15)+v(16)-2*v(18)+(w)*v(19)-v(20)+(w)
ii=3*v(13)+(w)*v(14)+(2*w)*v(16)-3*v(17)+(-w)*v(18)+(-2*w)*v(20)+3
ii=2*v(12)+(w)*v(13)-3*v(14)+(w)*v(15)-v(16)+(-w)*v(17)+v(18)+(-w)*v(19)-v(20)
ii=6*v(11)+(2*w)*v(12)-3*v(13)+(-3*w)*v(14)+(-4*w)*v(16)-3*v(17)+(w)*v(18)-6*v(19)+(2*w)*v(20)
ii=v(10)+v(12)-v(14)-v(16)
ii=3*v(9)+(-w)*v(10)+3*v(13)+(w)*v(14)+(2*w)*v(16)-3*v(17)+(-w)*v(18)+(-2*w)*v(20)
ii=v(8)
ii=v(7)
ii=2*v(6)+2*v(8)+(-w)*v(9)-v(10)-2*v(12)+(w)
ii=3*v(5)+(-w)*v(6)+3*v(9)+(w)*v(10)+(2*w)*v(12)-3*v(17)+(-w)*v(18)+(-2*w)*v(20)
ii=2*v(4)+(-w)*v(13)-3*v(14)-2*v(16)
ii=2*v(3)-3*v(13)+(w)*v(14)-2*v(15)
ii=2*v(2)+(w)*v(13)+v(14)+2*v(16)+(-w)*v(17)-v(18)-2*v(20)
ii=3*v(1)+(-w)*v(2)-3*v(5)+(-w)*v(6)+(-2*w)*v(8)+3*v(17)+(w)*v(18)+(2*w)*v(20)
ii=2*v(23)^2+(w)*v(17)*v(24)+v(18)*v(24)-2

对应坐标
//x=0+0*w
//y=0+0*w
//x=1+0*w
//y=0+0*w
//x=1/2+0*w
//y=0+1/2*w
//x=(0+0*w)*v(1)-(0+0*w)*(1)*v(2)+v(3)
//y=(0+0*w)*v(2)+(0+0*w)*(1)*v(1)+v(4)
//x=(1+0*w)*v(1)-(0+0*w)*(1)*v(2)+v(3)
//y=(1+0*w)*v(2)+(0+0*w)*(1)*v(1)+v(4)
//x=(1/2+0*w)*v(1)-(0+1/2*w)*(1)*v(2)+v(3)
//y=(1/2+0*w)*v(2)+(0+1/2*w)*(1)*v(1)+v(4)
//x=(1+0*w)*v(5)-(0+0*w)*(1)*v(6)+v(7)
//y=(1+0*w)*v(6)+(0+0*w)*(1)*v(5)+v(8)
//x=(1/2+0*w)*v(5)-(0+1/2*w)*(1)*v(6)+v(7)
//y=(1/2+0*w)*v(6)+(0+1/2*w)*(1)*v(5)+v(8)
//x=(1+0*w)*v(9)-(0+0*w)*(1)*v(10)+v(11)
//y=(1+0*w)*v(10)+(0+0*w)*(1)*v(9)+v(12)
//x=(1/2+0*w)*v(9)-(0+1/2*w)*(1)*v(10)+v(11)
//y=(1/2+0*w)*v(10)+(0+1/2*w)*(1)*v(9)+v(12)
//x=(1/2+0*w)*v(13)-(0+1/2*w)*(1)*v(14)+v(15)
//y=(1/2+0*w)*v(14)+(0+1/2*w)*(1)*v(13)+v(16)
//x=(1/2+0*w)*v(17)-(0+1/2*w)*(1)*v(18)+v(19)
//y=(1/2+0*w)*v(18)+(0+1/2*w)*(1)*v(17)+v(20)

关系图ABACAGAHBCBIBKCJCLDEDFDIDKEFEJELFGFHGHGIGJHKHLIJIKJLKL

mathe 发表于 2025-4-25 21:31:40

现在主要瓶颈在于通过脚本形式跨进程调用Singular过滤候选解，这个过程CPU利用率比较低。
按现在速度，预计可以在明后天产生n=17以前的解。
但是如果要处理更大范围的解，需要改进调用Singular的方式。刚刚看到可以在C/C++里面以Lib形式调用Singular,不过需要下载源码自己编译Singular,还需要学习一下使用方法。

mathe 发表于 2025-4-26 21:08:46

对于n=11, 排布
ABAHAIBJBKCDCECHCJDFDHDKEFEIEJFIFKGHGIGJGKHIJK
也比较有特点
它可以对应两个不同的图:


而n=10中排布
AIAJBCBDBEBHCFCGCHDEDFDIEGEJFGFIGJHIHJIJ
可以相同的图但是字母编号被置换了（需要注意这两个图都是动图，只是字母对应编号不同，这说明这个图存在到自己的自同构变换）

mathe 发表于 2025-4-27 09:54:59

n=13时30条边，只有一种关系图，但是应该有四种不同的画法，还不确定是否同构。
比如上面是两种画法

wayne 发表于 2025-4-27 10:03:22

是不是忽略长度关系的约束,仅根据点的邻接关系就可以判定是否同构.
在Mathematica有 IsomorphicGraphQ 函数可以用来判定两个图是否同构

mathe 发表于 2025-4-27 21:20:19

n=6到13的最优候选结果及对应方程（包含部分图）。
n=14比预想的要慢一些，应该明早能出来。但是15-17应该会快很多。

mathe 发表于 2025-4-28 08:59:42

n=14计算机搜索得到两种33边的候选解
ABAIAKALBIBMBNCFCJCKCLDEDJDKDMEJELENFJFMFNGHGIGKGMHIHLHNIJKLKMLNMN
ABAMANBFBGBHCFCGCICJDEDHDKDMEHELENFGFKFMGLGNHIHJIJIMINJKJLKLKMLNMN
每组有两种不同的方程，前者第二组方程虚数解，淘汰。后者两组解都是实数解。所以应该可以得到6个图


下面是其中一对图

mathe 发表于 2025-4-28 15:06:50

15-17的结果都出来了，不过里面部分singular文件有点太大，上传不了。
比如n=15, 只有AFAGAHAIBCBJBLBMCJCNCODEDKDLDNEKEMEOFGFKFLFMGKGNGOHIHJHLHNIJIMIOJKLMLNMONO
其中一个解坐标为（参数w为\(\sqrt{3}\))
//x=0+0*w
//y=0+0*w
//x=(0+0*w)*v(5)-(0+0*w)*(1)*v(6)+v(7)
//y=(0+0*w)*v(6)+(0+0*w)*(1)*v(5)+v(8)
//x=(1+0*w)*v(5)-(0+0*w)*(1)*v(6)+v(7)
//y=(1+0*w)*v(6)+(0+0*w)*(1)*v(5)+v(8)
//x=(0+0*w)*v(9)-(0+0*w)*(-1)*v(10)+v(11)
//y=(0+0*w)*v(10)+(0+0*w)*(-1)*v(9)+v(12)
//x=(1+0*w)*v(9)-(0+0*w)*(-1)*v(10)+v(11)
//y=(1+0*w)*v(10)+(0+0*w)*(-1)*v(9)+v(12)
//x=1+0*w
//y=0+0*w
//x=1/2+0*w
//y=0+1/2*w
//x=(1+0*w)*v(1)-(0+0*w)*(-1)*v(2)+v(3)
//y=(1+0*w)*v(2)+(0+0*w)*(-1)*v(1)+v(4)
//x=(1/2+0*w)*v(1)-(0+1/2*w)*(-1)*v(2)+v(3)
//y=(1/2+0*w)*v(2)+(0+1/2*w)*(-1)*v(1)+v(4)
//x=(3/2+0*w)*v(1)-(0+1/2*w)*(-1)*v(2)+v(3)
//y=(3/2+0*w)*v(2)+(0+1/2*w)*(-1)*v(1)+v(4)
//x=3/2+0*w
//y=0+1/2*w
//x=(1+0*w)*v(13)-(0+0*w)*(1)*v(14)+v(15)
//y=(1+0*w)*v(14)+(0+0*w)*(1)*v(13)+v(16)
//x=(1/2+0*w)*v(13)-(0+1/2*w)*(1)*v(14)+v(15)
//y=(1/2+0*w)*v(14)+(0+1/2*w)*(1)*v(13)+v(16)
//x=(1/2+0*w)*v(17)-(0+1/2*w)*(-1)*v(18)+v(19)
//y=(1/2+0*w)*v(18)+(0+1/2*w)*(-1)*v(17)+v(20)
//x=(1/2+0*w)*v(21)-(0+1/2*w)*(-1)*v(22)+v(23)
//y=(1/2+0*w)*v(22)+(0+1/2*w)*(-1)*v(21)+v(24)
参数满足方程
ii=3*v(27)+(w)*v(28)-8
ii=6*v(26)+(-w)*v(27)+3*v(28)+(-w)
ii=3*v(25)+(3*w)*v(26)+(2*w)*v(28)-3
ii=2*v(24)+(-w)*v(25)-v(26)-2*v(28)
ii=3*v(23)+(-w)*v(24)+(2*w)*v(26)-3*v(27)+(w)*v(28)-3
ii=2*v(22)+(w)*v(23)+v(24)+(-w)*v(25)+v(26)+(-w)*v(27)-v(28)
ii=3*v(21)+(-w)*v(22)+(-2*w)*v(24)+3*v(25)+(w)*v(26)+(2*w)*v(28)
ii=v(20)-v(26)-v(28)
ii=3*v(19)+(-w)*v(20)-3*v(25)+(w)*v(26)-3*v(27)+(w)*v(28)-3
ii=2*v(18)+(w)*v(19)+v(20)+(-w)*v(25)-v(26)+(-w)*v(27)-v(28)
ii=3*v(17)+(-w)*v(18)+(-2*w)*v(20)+(2*w)*v(26)+(2*w)*v(28)
ii=2*v(16)+(w)*v(17)+v(18)+(w)*v(19)-v(20)-2*v(22)+(-w)*v(23)-v(24)+(w)
ii=3*v(15)+(w)*v(16)+3*v(17)+(-w)*v(18)+(-2*w)*v(20)-3*v(21)+(-w)*v(22)-3*v(23)+(w)*v(24)
ii=2*v(14)+2*v(16)+(w)*v(17)-v(18)-2*v(20)+(w)
ii=3*v(13)+(-w)*v(14)-3*v(17)+(w)*v(18)+(2*w)*v(20)+3*v(21)+(-w)*v(22)+(-2*w)*v(24)
ii=2*v(12)+(w)*v(17)-v(18)-2*v(20)
ii=2*v(11)-v(17)+(-w)*v(18)-2*v(19)-2
ii=2*v(10)+2*v(12)+(w)*v(21)-v(22)-2*v(24)
ii=2*v(9)+2*v(11)-v(21)+(-w)*v(22)-2*v(23)-2
ii=v(8)-v(16)
ii=v(7)-v(15)
ii=2*v(6)+(w)*v(13)+v(14)+2*v(16)+(w)*v(21)-v(22)-2*v(24)
ii=2*v(5)+v(13)+(-w)*v(14)+2*v(15)-v(21)+(-w)*v(22)-2*v(23)
ii=v(4)
ii=v(3)
ii=2*v(2)-2*v(6)-2*v(8)+(-w)*v(21)+v(22)+2*v(24)
ii=2*v(1)-2*v(5)-2*v(7)+v(21)+(w)*v(22)+2*v(23)
ii=24*v(28)^2+27*v(25)+(9*w)*v(26)+39*v(27)+(-25*w)*v(28)-54
对应-44*v28*w + (24*v28^2 + 44)=0

n=16,只有一个配置AEAFAJAKBGBHBIBLCDCECFCHCIDGDJDKDLEFEMENFOFPGLGMGNHIHMHOINIPJKJMJOKNKPLOLPMNMONPOP
对应坐标
//x=0+0*w
//y=0+0*w
//x=(0+0*w)*v(1)-(0+0*w)*(-1)*v(2)+v(3)
//y=(0+0*w)*v(2)+(0+0*w)*(-1)*v(1)+v(4)
//x=3/2+0*w
//y=0+1/2*w
//x=(3/2+0*w)*v(5)-(0+1/2*w)*(1)*v(6)+v(7)
//y=(3/2+0*w)*v(6)+(0+1/2*w)*(1)*v(5)+v(8)
//x=1+0*w
//y=0+0*w
//x=1/2+0*w
//y=0+1/2*w
//x=(1+0*w)*v(9)-(0+0*w)*(-1)*v(10)+v(11)
//y=(1+0*w)*v(10)+(0+0*w)*(-1)*v(9)+v(12)
//x=(1+0*w)*v(1)-(0+0*w)*(-1)*v(2)+v(3)
//y=(1+0*w)*v(2)+(0+0*w)*(-1)*v(1)+v(4)
//x=(1/2+0*w)*v(1)-(0+1/2*w)*(-1)*v(2)+v(3)
//y=(1/2+0*w)*v(2)+(0+1/2*w)*(-1)*v(1)+v(4)
//x=(1+0*w)*v(5)-(0+0*w)*(1)*v(6)+v(7)
//y=(1+0*w)*v(6)+(0+0*w)*(1)*v(5)+v(8)
//x=(1/2+0*w)*v(5)-(0+1/2*w)*(1)*v(6)+v(7)
//y=(1/2+0*w)*v(6)+(0+1/2*w)*(1)*v(5)+v(8)
//x=(1/2+0*w)*v(9)-(0+1/2*w)*(-1)*v(10)+v(11)
//y=(1/2+0*w)*v(10)+(0+1/2*w)*(-1)*v(9)+v(12)
//x=(1+0*w)*v(13)-(0+0*w)*(1)*v(14)+v(15)
//y=(1+0*w)*v(14)+(0+0*w)*(1)*v(13)+v(16)
//x=(1/2+0*w)*v(13)-(0+1/2*w)*(1)*v(14)+v(15)
//y=(1/2+0*w)*v(14)+(0+1/2*w)*(1)*v(13)+v(16)
//x=(1/2+0*w)*v(17)-(0+1/2*w)*(-1)*v(18)+v(19)
//y=(1/2+0*w)*v(18)+(0+1/2*w)*(-1)*v(17)+v(20)
//x=(1/2+0*w)*v(21)-(0+1/2*w)*(-1)*v(22)+v(23)
//y=(1/2+0*w)*v(22)+(0+1/2*w)*(-1)*v(21)+v(24)
满足方程
ii=2*v(28)+(-w)
ii=2*v(27)-1
ii=3*v(25)+(w)*v(28)-4
ii=2*v(24)+(-w)*v(25)-v(26)+(w)*v(27)-v(28)+(-w)
ii=3*v(23)+(-w)*v(24)+(2*w)*v(26)-3*v(27)+(w)*v(28)-3
ii=2*v(22)+(w)*v(23)+v(24)+(-w)*v(25)+v(26)+(-w)*v(27)-v(28)
ii=3*v(21)+(-w)*v(22)+(-2*w)*v(24)+3*v(25)+(w)*v(26)+(2*w)*v(28)
ii=2*v(20)+(w)*v(21)-v(22)-2*v(24)+(w)*v(25)-v(26)+(w)*v(27)-v(28)
ii=3*v(19)+(-w)*v(20)-3*v(25)+(w)*v(26)-3*v(27)+(w)*v(28)-3
ii=2*v(18)+(w)*v(19)+v(20)+(-w)*v(25)-v(26)+(-w)*v(27)-v(28)
ii=3*v(17)+(-w)*v(18)+(-2*w)*v(20)+(2*w)*v(26)+(2*w)*v(28)
ii=v(16)
ii=v(15)-1
ii=2*v(14)+2*v(16)+(w)*v(17)-v(18)-2*v(20)+(w)
ii=3*v(13)+(-w)*v(14)-3*v(17)+(w)*v(18)+(2*w)*v(20)+3*v(21)+(-w)*v(22)+(-2*w)*v(24)
ii=2*v(12)+(-w)*v(13)-v(14)+(-w)*v(15)-v(16)+(w)*v(21)+v(22)+(w)*v(23)-v(24)
ii=6*v(11)+(-2*w)*v(12)+6*v(13)+(4*w)*v(14)+(4*w)*v(16)+3*v(21)+(-w)*v(22)+(-2*w)*v(24)-9*v(25)+(3*w)*v(26)-6*v(27)
ii=2*v(10)+2*v(12)+(-w)*v(13)-3*v(14)-2*v(16)
ii=3*v(9)+(w)*v(10)-3*v(13)+(-w)*v(14)+(-2*w)*v(16)-3*v(21)+(w)*v(22)+(2*w)*v(24)
ii=v(8)
ii=v(7)
ii=2*v(6)+(w)*v(9)-v(10)-2*v(12)+(-w)*v(21)+v(22)+2*v(24)
ii=3*v(5)+(-w)*v(6)-3*v(17)+(w)*v(18)+(2*w)*v(20)+3*v(21)+(-w)*v(22)+(-2*w)*v(24)
ii=v(4)-v(12)
ii=v(3)-v(11)
ii=2*v(2)+(-w)*v(9)+v(10)+2*v(12)+(w)*v(17)-v(18)-2*v(20)
ii=3*v(1)+(w)*v(2)+3*v(17)+(-w)*v(18)+(-2*w)*v(20)-3*v(21)+(w)*v(22)+(2*w)*v(24)
ii=3*v(26)^2+(-w)*v(25)*v(28)+4*v(25)-3
对应 -1/3*w + (3*v26^2 + 1/3)

n=17 候选解比较多，有
AHAMBCBDBEBMCKCMCPCQDEDLDNDPELEOEQFGFHFLFPFQGHGLGNGOHIHJIJIKINIPJKJOJQKLKMMNMONONPOQPQ
AOAQBEBGBJBOCDCFCHCIDIDKDNDQEJELENEQFHFLFMFQGKGNGOGPHLHNHPIKIMIPJLJMJPKLKOMOMPMQNPNQOQ
ALAMBHBIBJBLCFCGCKCMDEDFDGDJDLEHEIEKEMFGFNFPGOGQHIHNHPIOIQJLJNJOKMKPKQLPLQMNMONONPOQPQ
ALAMBEBGBHBMCFCICJCKDEDJDKDLDMEMEPEQFIFLFPFQGHGLGNGPHLHOHQILINIOJKJNJPKOKQMNMONONPOQPQ
ALAMBDBEBGBHCFCICJCKDEDLDNDOELEPEQFIFMFNFOGHGMGNGPHMHOHQIMIPIQJKJLJNJPKLKOKQLMNONPOQPQ
AGAMBCBDBEBFCDCLCPCQDLDNDOEFEKENEPFKFOFQGHGIGJGMHKHMHPHQIJILINIPJLJOJQKLKMMNMONONPOQPQ
ALAMBEBIBJBMCFCGCHCKDHDIDJDKDLELEMEPEQFGFLFNFPGLGOGQHKHPHQIJINIPJOJQKNKOLMMNMONONPOQPQ
ADAEAMBFBJBKBMCGCHCICLDFDHDIDMEGEJEKELFMFPFQGLGPGQHIHNHPIOIQJKJNJPKOKQLNLOMNMONONPOQPQ
ABACBFBGBKBLCHCICJCMDEDFDGDIDJEHEKELEMFGFNFOGPGQHMHNHOIJINIPJOJQKLKNKPLOLQMPMQNONPOQPQ
AEALAMBGBHBIBMCICJCKCMDFDJDKDLEFEGEHELFLFNFOGHGNGPHOHQIMIPIQJKJNJPKOKQLPLQMNMONONPOQPQ

mathe 发表于 2025-5-3 10:51:26

现在试验了一下，计算到n=21问题不大，但是要计算n=22就比较麻烦，对内存开销和计算时间都要求有点太高(特别是计算时间)。
现在经过优化后可以半天之内给出n=21的结果了,但是计算n=22的时间还是很难估计，有点过于复杂。
对比了一下wayne给出的文章，里面给出了几种方法
i）先对于n较少情况，找出一些非法子图，然后对于较大图，通过匹配是否包含这些非法子图，可以裁剪很多
ii)如果求n个点m条边的的问题，我们可以先从n-1个点，不少于m-边的情况增加一个点来构造
iii)对于n 较少情况，可以找出一些子图，这些子图的合法排布中必然会包含两个不相邻的点距离必须是1，那么这些必然不是最大图，同样任何包含这样子图的图也不是最大图，可以裁剪
iv)论文里面关键的裁剪计算方案，没有看懂。
我现在采用方法的一点区别是
对于i)我采用的是对于n个点的图，选择去点一个点后判断是否还是合法n-1个点的图（查询所有n-1个点的图构成的集合）
对于ii)我利用了果树问题分析中的方案，使用了更加优秀的裁剪方案，对于n个点m条边的图，去掉一个点后，得到的图边数不少于n-而且边数加最小度数不小于m-1.
对于iii)比较奇怪，我现在还没能成功使用
对于iv)我使用了自己14#中提到的连通区域嵌入方案再Singular求解，效率还不错。当然解方程过程中会遇到部分方程需要比较时间来求解，这时程序里面就做了限时，太长时间没有计算出来就算通过。

查看完整版本: 一个著名题目——等距排布问题