数学研发网设为首页收藏本站
切换到窄版

 找回密码
 欢迎注册
数学研发论坛»论坛 › 【数学研究】 › 趣题妙解 › 一个著名题目——等距排布问题
1234567下一页
返回列表 发新帖
楼主: shshsh_0510

[讨论] 一个著名题目——等距排布问题

[复制链接]
mathe
发表于 2025-4-25 14:23:25 | 显示全部楼层
试了一下n=8中的文件
ABAEAFBGBHCDCECGDFDHEFEGFHGH.sg.8
对应的解含有一个变参，所有对应的是一系列图
8.2.png
可以通过geogebra制作出动图 8.2.ggb (26.36 KB, 下载次数: 4)

点评

wayne
挺好玩的  发表于 2025-4-25 15:51

评分

参与人数 1威望 +6 金币 +6 贡献 +6 经验 +6 鲜花 +6 收起 理由
wayne + 6 + 6 + 6 + 6 + 6

查看全部评分

毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mathe
发表于 2025-4-25 19:51:40 | 显示全部楼层
n=12也应该是动图，含有一个参数，方程为
  1. ii[1]=v(22)
  2. ii[2]=3*v(21)+(-w)*v(22)-3
  3. ii[3]=2*v(20)+(-w)
  4. ii[4]=2*v(19)-1
  5. ii[5]=2*v(18)+(-w)*v(19)+v(20)-2*v(22)+(w)*v(23)-v(24)
  6. ii[6]=3*v(17)+(w)*v(18)+(2*w)*v(20)-3*v(21)+(-w)*v(22)+(-2*w)*v(24)
  7. ii[7]=v(16)
  8. ii[8]=v(15)-1
  9. ii[9]=2*v(14)+(-w)*v(15)+v(16)-2*v(18)+(w)*v(19)-v(20)+(w)
  10. ii[10]=3*v(13)+(w)*v(14)+(2*w)*v(16)-3*v(17)+(-w)*v(18)+(-2*w)*v(20)+3
  11. ii[11]=2*v(12)+(w)*v(13)-3*v(14)+(w)*v(15)-v(16)+(-w)*v(17)+v(18)+(-w)*v(19)-v(20)
  12. ii[12]=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)
  13. ii[13]=v(10)+v(12)-v(14)-v(16)
  14. ii[14]=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)
  15. ii[15]=v(8)
  16. ii[16]=v(7)
  17. ii[17]=2*v(6)+2*v(8)+(-w)*v(9)-v(10)-2*v(12)+(w)
  18. ii[18]=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)
  19. ii[19]=2*v(4)+(-w)*v(13)-3*v(14)-2*v(16)
  20. ii[20]=2*v(3)-3*v(13)+(w)*v(14)-2*v(15)
  21. ii[21]=2*v(2)+(w)*v(13)+v(14)+2*v(16)+(-w)*v(17)-v(18)-2*v(20)
  22. ii[22]=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)
  23. ii[23]=2*v(23)^2+(w)*v(17)*v(24)+v(18)*v(24)-2
复制代码

对应坐标
  1. //x[A]=0+0*w
  2. //y[A]=0+0*w
  3. //x[B]=1+0*w
  4. //y[B]=0+0*w
  5. //x[C]=1/2+0*w
  6. //y[C]=0+1/2*w
  7. //x[D]=(0+0*w)*v(1)-(0+0*w)*(1)*v(2)+v(3)
  8. //y[D]=(0+0*w)*v(2)+(0+0*w)*(1)*v(1)+v(4)
  9. //x[E]=(1+0*w)*v(1)-(0+0*w)*(1)*v(2)+v(3)
  10. //y[E]=(1+0*w)*v(2)+(0+0*w)*(1)*v(1)+v(4)
  11. //x[F]=(1/2+0*w)*v(1)-(0+1/2*w)*(1)*v(2)+v(3)
  12. //y[F]=(1/2+0*w)*v(2)+(0+1/2*w)*(1)*v(1)+v(4)
  13. //x[G]=(1+0*w)*v(5)-(0+0*w)*(1)*v(6)+v(7)
  14. //y[G]=(1+0*w)*v(6)+(0+0*w)*(1)*v(5)+v(8)
  15. //x[H]=(1/2+0*w)*v(5)-(0+1/2*w)*(1)*v(6)+v(7)
  16. //y[H]=(1/2+0*w)*v(6)+(0+1/2*w)*(1)*v(5)+v(8)
  17. //x[I]=(1+0*w)*v(9)-(0+0*w)*(1)*v(10)+v(11)
  18. //y[I]=(1+0*w)*v(10)+(0+0*w)*(1)*v(9)+v(12)
  19. //x[J]=(1/2+0*w)*v(9)-(0+1/2*w)*(1)*v(10)+v(11)
  20. //y[J]=(1/2+0*w)*v(10)+(0+1/2*w)*(1)*v(9)+v(12)
  21. //x[K]=(1/2+0*w)*v(13)-(0+1/2*w)*(1)*v(14)+v(15)
  22. //y[K]=(1/2+0*w)*v(14)+(0+1/2*w)*(1)*v(13)+v(16)
  23. //x[L]=(1/2+0*w)*v(17)-(0+1/2*w)*(1)*v(18)+v(19)
  24. //y[L]=(1/2+0*w)*v(18)+(0+1/2*w)*(1)*v(17)+v(20)
复制代码

关系图ABACAGAHBCBIBKCJCLDEDFDIDKEFEJELFGFHGHGIGJHKHLIJIKJLKL
v12.1.png
v12.1.ggb (26.25 KB, 下载次数: 0)
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

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

点评

mathe
计算n=13时发现了代码中bug，这部分要重跑了  发表于 2025-4-26 21:09

评分

参与人数 1威望 +12 金币 +12 贡献 +12 经验 +12 鲜花 +12 收起 理由
wayne + 12 + 12 + 12 + 12 + 12 神马都是浮云

查看全部评分

毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mathe
发表于 2025-4-26 21:08:46 | 显示全部楼层
对于n=11, 排布
ABAHAIBJBKCDCECHCJDFDHDKEFEIEJFIFKGHGIGJGKHIJK
也比较有特点
它可以对应两个不同的图:
v11.1.png v11.2.png

而n=10中排布
AIAJBCBDBEBHCFCGCHDEDFDIEGEJFGFIGJHIHJIJ
可以相同的图但是字母编号被置换了（需要注意这两个图都是动图，只是字母对应编号不同，这说明这个图存在到自己的自同构变换）
10.1.png 10.2.png
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mathe
发表于 2025-4-27 09:54:59 | 显示全部楼层
v13.png

n=13时30条边，只有一种关系图，但是应该有四种不同的画法，还不确定是否同构。
比如上面是两种画法
13.zip (29.65 KB, 下载次数: 3)
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

wayne
发表于 2025-4-27 10:03:22 | 显示全部楼层
是不是忽略长度关系的约束,仅根据点的邻接关系就可以判定是否同构.
在Mathematica有 IsomorphicGraphQ 函数可以用来判定两个图是否同构

点评

mathe
而一个群自同构数目应该就可以描述被求解后重复出现的数目。  发表于 2025-5-4 06:27
mathe
找出一个图的所有自同构变换，就可以将一个解变换到另外一个解。特别对于含参的结果，采用自同构群来判断更合理。  发表于 2025-5-4 06:26
wayne
确实. 明白了  发表于 2025-4-27 19:54
mathe
我们需要在平移和旋转变换下等价的关系，已经有所有点坐标，其实不难。先求重心，然后平移将重心重合，在计算各点到重心距离看看能否匹配到唯一距离匹配点，如果没有就对多种可能枚举一下   发表于 2025-4-27 12:01
mathe
相同连接关系可以有多个图，比如前面一些带自由度的  发表于 2025-4-27 11:45
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mathe
发表于 2025-4-27 21:20:19 | 显示全部楼层
等距.zip (529.39 KB, 下载次数: 3)
n=6到13的最优候选结果及对应方程（包含部分图）。
n=14比预想的要慢一些，应该明早能出来。但是15-17应该会快很多。
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mathe
发表于 2025-4-28 08:59:42 | 显示全部楼层
n=14计算机搜索得到两种33边的候选解
ABAIAKALBIBMBNCFCJCKCLDEDJDKDMEJELENFJFMFNGHGIGKGMHIHLHNIJKLKMLNMN
ABAMANBFBGBHCFCGCICJDEDHDKDMEHELENFGFKFMGLGNHIHJIJIMINJKJLKLKMLNMN
每组有两种不同的方程，前者第二组方程虚数解，淘汰。后者两组解都是实数解。所以应该可以得到6个图

14.zip (90.86 KB, 下载次数: 2)
下面是其中一对图
v14.1.png v14.2.png
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mathe
发表于 2025-4-28 15:06:50 | 显示全部楼层
15-17的结果都出来了，不过里面部分singular文件有点太大，上传不了。
比如n=15, 只有AFAGAHAIBCBJBLBMCJCNCODEDKDLDNEKEMEOFGFKFLFMGKGNGOHIHJHLHNIJIMIOJKLMLNMONO
其中一个解坐标为（参数w为\(\sqrt{3}\))
//x[A]=0+0*w
//y[A]=0+0*w
//x[B]=(0+0*w)*v(5)-(0+0*w)*(1)*v(6)+v(7)
//y[B]=(0+0*w)*v(6)+(0+0*w)*(1)*v(5)+v(8)
//x[C]=(1+0*w)*v(5)-(0+0*w)*(1)*v(6)+v(7)
//y[C]=(1+0*w)*v(6)+(0+0*w)*(1)*v(5)+v(8)
//x[D]=(0+0*w)*v(9)-(0+0*w)*(-1)*v(10)+v(11)
//y[D]=(0+0*w)*v(10)+(0+0*w)*(-1)*v(9)+v(12)
//x[E]=(1+0*w)*v(9)-(0+0*w)*(-1)*v(10)+v(11)
//y[E]=(1+0*w)*v(10)+(0+0*w)*(-1)*v(9)+v(12)
//x[F]=1+0*w
//y[F]=0+0*w
//x[G]=1/2+0*w
//y[G]=0+1/2*w
//x[H]=(1+0*w)*v(1)-(0+0*w)*(-1)*v(2)+v(3)
//y[H]=(1+0*w)*v(2)+(0+0*w)*(-1)*v(1)+v(4)
//x[I]=(1/2+0*w)*v(1)-(0+1/2*w)*(-1)*v(2)+v(3)
//y[I]=(1/2+0*w)*v(2)+(0+1/2*w)*(-1)*v(1)+v(4)
//x[J]=(3/2+0*w)*v(1)-(0+1/2*w)*(-1)*v(2)+v(3)
//y[J]=(3/2+0*w)*v(2)+(0+1/2*w)*(-1)*v(1)+v(4)
//x[K]=3/2+0*w
//y[K]=0+1/2*w
//x[L]=(1+0*w)*v(13)-(0+0*w)*(1)*v(14)+v(15)
//y[L]=(1+0*w)*v(14)+(0+0*w)*(1)*v(13)+v(16)
//x[M]=(1/2+0*w)*v(13)-(0+1/2*w)*(1)*v(14)+v(15)
//y[M]=(1/2+0*w)*v(14)+(0+1/2*w)*(1)*v(13)+v(16)
//x[N]=(1/2+0*w)*v(17)-(0+1/2*w)*(-1)*v(18)+v(19)
//y[N]=(1/2+0*w)*v(18)+(0+1/2*w)*(-1)*v(17)+v(20)
//x[O]=(1/2+0*w)*v(21)-(0+1/2*w)*(-1)*v(22)+v(23)
//y[O]=(1/2+0*w)*v(22)+(0+1/2*w)*(-1)*v(21)+v(24)
参数满足方程
ii[1]=3*v(27)+(w)*v(28)-8
ii[2]=6*v(26)+(-w)*v(27)+3*v(28)+(-w)
ii[3]=3*v(25)+(3*w)*v(26)+(2*w)*v(28)-3
ii[4]=2*v(24)+(-w)*v(25)-v(26)-2*v(28)
ii[5]=3*v(23)+(-w)*v(24)+(2*w)*v(26)-3*v(27)+(w)*v(28)-3
ii[6]=2*v(22)+(w)*v(23)+v(24)+(-w)*v(25)+v(26)+(-w)*v(27)-v(28)
ii[7]=3*v(21)+(-w)*v(22)+(-2*w)*v(24)+3*v(25)+(w)*v(26)+(2*w)*v(28)
ii[8]=v(20)-v(26)-v(28)
ii[9]=3*v(19)+(-w)*v(20)-3*v(25)+(w)*v(26)-3*v(27)+(w)*v(28)-3
ii[10]=2*v(18)+(w)*v(19)+v(20)+(-w)*v(25)-v(26)+(-w)*v(27)-v(28)
ii[11]=3*v(17)+(-w)*v(18)+(-2*w)*v(20)+(2*w)*v(26)+(2*w)*v(28)
ii[12]=2*v(16)+(w)*v(17)+v(18)+(w)*v(19)-v(20)-2*v(22)+(-w)*v(23)-v(24)+(w)
ii[13]=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[14]=2*v(14)+2*v(16)+(w)*v(17)-v(18)-2*v(20)+(w)
ii[15]=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[16]=2*v(12)+(w)*v(17)-v(18)-2*v(20)
ii[17]=2*v(11)-v(17)+(-w)*v(18)-2*v(19)-2
ii[18]=2*v(10)+2*v(12)+(w)*v(21)-v(22)-2*v(24)
ii[19]=2*v(9)+2*v(11)-v(21)+(-w)*v(22)-2*v(23)-2
ii[20]=v(8)-v(16)
ii[21]=v(7)-v(15)
ii[22]=2*v(6)+(w)*v(13)+v(14)+2*v(16)+(w)*v(21)-v(22)-2*v(24)
ii[23]=2*v(5)+v(13)+(-w)*v(14)+2*v(15)-v(21)+(-w)*v(22)-2*v(23)
ii[24]=v(4)
ii[25]=v(3)
ii[26]=2*v(2)-2*v(6)-2*v(8)+(-w)*v(21)+v(22)+2*v(24)
ii[27]=2*v(1)-2*v(5)-2*v(7)+v(21)+(w)*v(22)+2*v(23)
ii[28]=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[A]=0+0*w
//y[A]=0+0*w
//x[B]=(0+0*w)*v(1)-(0+0*w)*(-1)*v(2)+v(3)
//y[B]=(0+0*w)*v(2)+(0+0*w)*(-1)*v(1)+v(4)
//x[C]=3/2+0*w
//y[C]=0+1/2*w
//x[D]=(3/2+0*w)*v(5)-(0+1/2*w)*(1)*v(6)+v(7)
//y[D]=(3/2+0*w)*v(6)+(0+1/2*w)*(1)*v(5)+v(8)
//x[E]=1+0*w
//y[E]=0+0*w
//x[F]=1/2+0*w
//y[F]=0+1/2*w
//x[G]=(1+0*w)*v(9)-(0+0*w)*(-1)*v(10)+v(11)
//y[G]=(1+0*w)*v(10)+(0+0*w)*(-1)*v(9)+v(12)
//x[H]=(1+0*w)*v(1)-(0+0*w)*(-1)*v(2)+v(3)
//y[H]=(1+0*w)*v(2)+(0+0*w)*(-1)*v(1)+v(4)
//x[I]=(1/2+0*w)*v(1)-(0+1/2*w)*(-1)*v(2)+v(3)
//y[I]=(1/2+0*w)*v(2)+(0+1/2*w)*(-1)*v(1)+v(4)
//x[J]=(1+0*w)*v(5)-(0+0*w)*(1)*v(6)+v(7)
//y[J]=(1+0*w)*v(6)+(0+0*w)*(1)*v(5)+v(8)
//x[K]=(1/2+0*w)*v(5)-(0+1/2*w)*(1)*v(6)+v(7)
//y[K]=(1/2+0*w)*v(6)+(0+1/2*w)*(1)*v(5)+v(8)
//x[L]=(1/2+0*w)*v(9)-(0+1/2*w)*(-1)*v(10)+v(11)
//y[L]=(1/2+0*w)*v(10)+(0+1/2*w)*(-1)*v(9)+v(12)
//x[M]=(1+0*w)*v(13)-(0+0*w)*(1)*v(14)+v(15)
//y[M]=(1+0*w)*v(14)+(0+0*w)*(1)*v(13)+v(16)
//x[N]=(1/2+0*w)*v(13)-(0+1/2*w)*(1)*v(14)+v(15)
//y[N]=(1/2+0*w)*v(14)+(0+1/2*w)*(1)*v(13)+v(16)
//x[O]=(1/2+0*w)*v(17)-(0+1/2*w)*(-1)*v(18)+v(19)
//y[O]=(1/2+0*w)*v(18)+(0+1/2*w)*(-1)*v(17)+v(20)
//x[P]=(1/2+0*w)*v(21)-(0+1/2*w)*(-1)*v(22)+v(23)
//y[P]=(1/2+0*w)*v(22)+(0+1/2*w)*(-1)*v(21)+v(24)
满足方程
ii[1]=2*v(28)+(-w)
ii[2]=2*v(27)-1
ii[3]=3*v(25)+(w)*v(28)-4
ii[4]=2*v(24)+(-w)*v(25)-v(26)+(w)*v(27)-v(28)+(-w)
ii[5]=3*v(23)+(-w)*v(24)+(2*w)*v(26)-3*v(27)+(w)*v(28)-3
ii[6]=2*v(22)+(w)*v(23)+v(24)+(-w)*v(25)+v(26)+(-w)*v(27)-v(28)
ii[7]=3*v(21)+(-w)*v(22)+(-2*w)*v(24)+3*v(25)+(w)*v(26)+(2*w)*v(28)
ii[8]=2*v(20)+(w)*v(21)-v(22)-2*v(24)+(w)*v(25)-v(26)+(w)*v(27)-v(28)
ii[9]=3*v(19)+(-w)*v(20)-3*v(25)+(w)*v(26)-3*v(27)+(w)*v(28)-3
ii[10]=2*v(18)+(w)*v(19)+v(20)+(-w)*v(25)-v(26)+(-w)*v(27)-v(28)
ii[11]=3*v(17)+(-w)*v(18)+(-2*w)*v(20)+(2*w)*v(26)+(2*w)*v(28)
ii[12]=v(16)
ii[13]=v(15)-1
ii[14]=2*v(14)+2*v(16)+(w)*v(17)-v(18)-2*v(20)+(w)
ii[15]=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[16]=2*v(12)+(-w)*v(13)-v(14)+(-w)*v(15)-v(16)+(w)*v(21)+v(22)+(w)*v(23)-v(24)
ii[17]=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[18]=2*v(10)+2*v(12)+(-w)*v(13)-3*v(14)-2*v(16)
ii[19]=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[20]=v(8)
ii[21]=v(7)
ii[22]=2*v(6)+(w)*v(9)-v(10)-2*v(12)+(-w)*v(21)+v(22)+2*v(24)
ii[23]=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[24]=v(4)-v(12)
ii[25]=v(3)-v(11)
ii[26]=2*v(2)+(-w)*v(9)+v(10)+2*v(12)+(w)*v(17)-v(18)-2*v(20)
ii[27]=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[28]=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-[2n/m]边的情况增加一个点来构造
iii)对于n 较少情况，可以找出一些子图，这些子图的合法排布中必然会包含两个不相邻的点距离必须是1，那么这些必然不是最大图，同样任何包含这样子图的图也不是最大图，可以裁剪
iv)论文里面关键的裁剪计算方案，没有看懂。
我现在采用方法的一点区别是
对于i)我采用的是对于n个点的图，选择去点一个点后判断是否还是合法n-1个点的图（查询所有n-1个点的图构成的集合）
对于ii)我利用了果树问题分析中的方案，使用了更加优秀的裁剪方案，对于n个点m条边的图，去掉一个点后，得到的图边数不少于n-[2m/n]而且边数加最小度数不小于m-1.
对于iii)比较奇怪，我现在还没能成功使用
对于iv)我使用了自己14#中提到的连通区域嵌入方案再Singular求解，效率还不错。当然解方程过程中会遇到部分方程需要比较时间来求解，这时程序里面就做了限时，太长时间没有计算出来就算通过。
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

1234567下一页
返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2025-5-17 12:42 , Processed in 0.093834 second(s), 18 queries .

Powered by Discuz! X3.5

© 2001-2025 Discuz! Team.

快速回复 返回顶部 返回列表