一个著名题目——等距排布问题

wayne

这种算法是否可行，就是在n个顶点的情况下，对于每个j, 0<j<n，计算出最优子图g(n-j)和g(j)，以及子图之间构成的 j*(n-j)个新边的个数最多的解。最终找出最大的j。完成构图。
或者，我们倒过来： 对于已知的最优图g(n)，是不是 我们总能找到一个1+1的子图拆分，使得g(n-j)和g(j)本身也是最优子图。

wayne

mathe 发表于 2025-5-7 08:00
数据更新一下，修复wanye发现的一些问题(n=22的还没有完全处理，也没有完全修复，后面继续处理) ...

论坛评论没有消息提醒.碰巧回看了一下.
我也发现只给数字会重名,但是完整的文件名又太长,所以我就加了两个变量, 一个是该文件在目录里按照文件名字典排序的索引编号,另一个是该文件的方程的解的个数的索引.
当前目录/点数/数字编号-该文件在当前目录下的文件索引号-解的索引号.

比如拿这个作为例子:  https://nestwhile.com/res/alld/18/148-3-2.png, 就是 ls -l 按照文件名排序,第3个文件的第二个解.因为该文件有两个解,所以还有一个就是https://nestwhile.com/res/alld/18/148-3-1.png
ABACANAQBCBOBRCHCPDEDIDQDREIELEMFGFJFLFQGJGMGRHKHNHOHPIJINIOJKJPKLKMKPLMLNLQMOMRNONQORPQPRQR.sg.148.geo

如果不合适，我随时可以改，改起来很容易，提要求就行。我感觉我这里的文件名索引也不太好。

mathe

这个附件给出了已知的22点60线的解，对于只含一个简单二次方程情况做了提前处理，把数值解以注释形式放入文件中，改名为.sol
可以看出除了一个文件，其余的都是这种形式
22.tgz (233.75 KB, 下载次数: 3)

6 天前 上传

点击文件名下载附件

mathe

n=4的解为(4/00-1-1):



n=5的解有(5/00-1-1), 显然是4/00-1-1的基础上添加一个点:


n=6有一下几个:
6/0-1-m，这个是n=2和n=3的笛卡尔积形式，带有额外自由度:


6/00-2-1, 显然是5/00-1-1的基础上添加了一个点:


6/00-3-1, 也是5/00-1-1的基础上添加了一个点：


6/00-4-1，也是5/00-1-1的基础上添加了一个点：


n=7,只有一个解7/00-1-1, 为6/00-4-1的基础上添加一个点:


n=8的解比较多，有
8/0-2-m，这个为n=4(4/00-1-1)和n=2的笛卡尔积形式:

8/0-3-m (8/3-4-m), 这个可以看成6/0-1-m添加两个点构成，也可以看成两个6/0-1-m经过旋转后部分重叠合成

8/00-1-1 很多点重叠，是增根，需要淘汰
8/00-5-1， 是7/00-1-1增加一个点构成：

mathe

n=9只有一个解，做了两个图9/0-1-m 和9/19-2-m, 为8/0-3-m添加一个点构成

n=10有两组动态解，24#中给出下面的解，为9/0-1-m添加一个点构成，（10/16-1-m和10/32-2-m)
由于是动态图，其实这个额外添加点在不同动图位置看起来会完成不同

n=11的图有
11/12-3-m，很显然是9/0-1-m添加一个点构成n=10时，9个点位置相同的情况下可以有两个不同方向的添加点，它们之间距离是1，合并在一下：

11/18-1-1 (11/18-1-2,11/28-2-1,11/28-2-2,11/31-4-m)， 和前一个类似原理产生

mathe

n=12也是动图， 12/0-1-m, 12/26-2-m, 可以看成n=11情况再添加一个点，也可以看成n=4（4/00-1-1）和n=3的笛卡尔积


n=13,13/39-1-1,13/39-1-2,13/61-2-1, 13/61-2-2 是在12/0-1-m基础上添加一个点：

mathe

n=14, 多个图比较复杂
14/125-1-1，14/125-1-2, 14/54-2-1, 14/54-2-2  这个图比较难以识别，它其实是n=16的情况去掉两个点。而n=16(16/126-1-1)情况其实是n=4和n=4的笛卡尔积在添加一条额外边


而另外一组包含3度点，显然是从n=13添加一个点得到

mathe

n=15 15/120-1-1 15/120-1-2 15/53-2-1 15/53-2-2 是n=16去掉一个点


n=16 16/126-1-1 16/126-1-2 16/53-2-1 16/53-2-2 就是n=4和n=4的笛卡尔积添加额外边(黑色)（由于每次笛卡尔积产生一个额外自由度，结果含两自由度，可以额外添加边），所以图中菱形众多

mathe

n=17的图有三类，由于最优解43边只比n=16的最优解41边多两边，
所以第一大类是n=16的最优解添加一点，到n=16中两个点距离都是1.
114-19-1：

114-19-2：

117-15-1：

117-15-2：

125-5-1：

125-5-2：

14-10-1：

14-10-2：

14-13-1：

14-13-2：

147-9-1:

147-9-2:

155-11-1:

155-11-2:

54-6-1:

54-6-2:

59-14-1:

59-14-2:

6-12-1:

6-12-2:

65-20-1：

65-20-2：

67-16-1:

67-16-2:


然后我们发现此外还有很多图，做出来的图丢了一点，其实对应的A点是复数点，也就是它需要到两个相互距离大于2的点的距离都是1，实际上需要淘汰掉，比如包含图:
126-1-1: (需要AB=AC=1,而BC距离显然远远大于1)

此外还有126-1-2,14-7-1,14-7-2,15-17-1,15-17-2,53-2-1,53-2-2,57-18-1,57-18-2,59-8-1,59-8-2.

第三类最小点度数为3，它们都是直接n=4和n=4的笛卡尔积(不添加额外边)上再加一个三度点A,有
12-3-1：

12-3-2：

58-4-1：

58-4-2：

mathe

为了规律性，下一个我们先分析n=20, 可以看出全部为n=4和n=5的笛卡尔积再加上一条额外黑边:
150-1-1:

150-1-2:

238-2-1:

238-2-2: