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

mathe

可以考虑计算机穷举n个点之间若干点有连接的不等价方案图，当然我们知道不可以有\(K_4\)子图（也就是任意四个点不能两两之间有连线），而且对于任何两个点A,B，同时和A,B都相邻的点最多两个。
4个点五条边的方案是唯一:
ACADBCBDCD (其中不同字母代表不同的点，顺序两个相邻的字母代表一条边，所以这里代表5条边AC, AD, BC, BD, CD)
   这好是4个点符合条件的答案
5个点最多7条边，计算机穷举7条边结果只有
ACAEBDBECDCEDE

但是穷举6个点最多10条边，其中10条边的图为
ABACAFBDBFCECFDEDFEF
由于这个图中同时存在三角形DEF,BDF,这两个正三角形有公共边DF,确定了这四个点的图。
另外ABE和CEF又是三角形，于是又唯一确定了A,C两个点，但是还要求AC长度为1，如下图

这个显然是不合法的，需要淘汰。
而6个点9条边的有下面5种
ADAEBDBFCECFDEDFEF
ABACADBCBECFDEDFEF
ACAEBDBFCECFDEDFEF
ADAFBEBFCDCECFDFEF
ABACBDBFCECFDEDFEF(非法)
根据楼主帖子中内容，应该其中4种合法

类似对于7个点，我们从6各点合法情况去扩展，可以得到下面4种12条边方案
ABACAEBDBFCECGDFDGEFEGFG
ABACADBEBFCECGDFDGEFEGFG
ABACAGBEBGCFCGDEDFDGEGFG （G和所有其它点相邻，是合法解）
AEAFBCBDBGCECGDFDGEFEGFG

wayne

这还挺巧的, 找到一篇2025年2月的文章,还挺新的: https://arxiv.org/abs/2412.11914
2412.11914v2.pdf (472.21 KB, 下载次数: 13)

2025-4-20 16:28 上传

点击文件名下载附件

1. data = StringSplit[
   
2.     ToString[
   
3.      Import["/Users/zuse/Desktop/2412.11914v2.pdf",
   
4.        "PagePlaintext"][[-1]]], RegularExpression["\\s+"]][[14 ;; -2]];
   
5. graph = Association[]; Do[
   
6. If[StringStartsQ[line, DigitCharacter], n = FromDigits[line];
   
7.   graph[n] = {}, AppendTo[graph[n], ">>graph6<<" <> line]], {line,
   
8.   data}]; graph

复制代码

1. {1,0}
   
2. {2,1}
   
3. {3,3}
   
4. {4,5}
   
5. {5,7}
   
6. {6,9}
   
7. {7,12}
   
8. {8,14}
   
9. {9,18}
   
10. {10,20}
    
11. {11,23}
    
12. {12,27}
    
13. {13,30}
    
14. {14,33}
    
15. {15,37}
    
16. {16,41}
    
17. {17,43}
    
18. {18,46}
    
19. {19,50}
    
20. {20,54}
    
21. {21,57}
    

复制代码

这篇论文提到了图的一种ascii表达格式,叫做graph6.蛮有趣的
我用Mathematica解析PDF得出来了,但是发现有部分格式不对.主要是单引号这个字符不识别.但是文档里确实是单引号.

1. {0, 0, ">>graph6<<?", {}}
   
2. {1, 0, ">>graph6<<@", {}}
   
3. {2, 1, ">>graph6<<A_", {1 -> 2}}
   
4. {3, 3, ">>graph6<<Bw", {1 -> 2, 1 -> 3, 2 -> 3}}
   
5. {4, 5, ">>graph6<<C^", {1 -> 3, 1 -> 4, 2 -> 3, 2 -> 4, 3 -> 4}}
   
6. {5, 7, ">>graph6<<DR{", {1 -> 3, 1 -> 5, 2 -> 4, 2 -> 5, 3 -> 4, 3 -> 5, 4 -> 5}}
   
7. {6, 9, ">>graph6<<E{Sw", {1 -> 2, 1 -> 3, 1 -> 4, 2 -> 3, 2 -> 5, 3 -> 6, 4 -> 5, 4 -> 6, 5 -> 6}}
   
8. {6, 9, ">>graph6<<EDZw", {1 -> 4, 1 -> 6, 2 -> 5, 2 -> 6, 3 -> 4, 3 -> 5, 3 -> 6, 4 -> 6, 5 -> 6}}
   
9. {6, 9, ">>graph6<<EQlw", {1 -> 3, 1 -> 5, 2 -> 4, 2 -> 6, 3 -> 5, 3 -> 6, 4 -> 5, 4 -> 6, 5 -> 6}}
   
10. {6, 9, ">>graph6<<EElw", {1 -> 4, 1 -> 5, 2 -> 4, 2 -> 6, 3 -> 5, 3 -> 6, 4 -> 5, 4 -> 6, 5 -> 6}}
    
11. {7, 12, ">>graph6<<FoSvw", {1 -> 2, 1 -> 3, 1 -> 7, 2 -> 5, 2 -> 7, 3 -> 6, 3 -> 7, 4 -> 5, 4 -> 6, 4 -> 7, 5 -> 7, 6 -> 7}}
    
12. {8, 14, ">>graph6<<G`iiqk", {1 -> 2, 1 -> 5, 1 -> 6, 2 -> 7, 2 -> 8, 3 -> 4, 3 -> 5, 3 -> 6, 4 -> 7, 4 -> 8, 5 -> 6, 5 -> 7, 6 -> 8, 7 -> 8}}
    
13. {8, 14, ">>graph6<<G`iZQk", {1 -> 2, 1 -> 5, 1 -> 6, 2 -> 7, 2 -> 8, 3 -> 4, 3 -> 5, 3 -> 7, 4 -> 6, 4 -> 8, 5 -> 6, 5 -> 7, 6 -> 8, 7 -> 8}}
    
14. {8, 14, ">>graph6<<GIISZ{", {1 -> 6, 1 -> 7, 2 -> 3, 2 -> 4, 2 -> 8, 3 -> 5, 3 -> 8, 4 -> 6, 4 -> 8, 5 -> 7, 5 -> 8, 6 -> 7, 6 -> 8, 7 -> 8}}
    
15. {9, 18, ">>graph6<<H{dQXgj", {1 -> 2, 1 -> 3, 1 -> 4, 1 -> 5, 2 -> 3, 2 -> 6, 2 -> 7, 3 -> 8, 3 -> 9, 4 -> 5, 4 -> 6, 4 -> 8, 5 -> 7, 5 -> 9, 6 -> 7, 6 -> 8, 7 -> 9, 8 -> 9}}
    
16. {10, 20, ">>graph6<<IISpZATaw", {1 -> 9, 1 -> 10, 2 -> 3, 2 -> 4, 2 -> 5, 2 -> 8, 3 -> 6, 3 -> 7, 3 -> 8, 4 -> 5, 4 -> 6, 4 -> 9, 5 -> 7, 5 -> 10, 6 -> 7, 6 -> 9, 7 -> 10, 8 -> 9, 8 -> 10, 9 -> 10}}
    
17. {11, 23, ">>graph6<<J`GWDeNYak_", {1 -> 2, 1 -> 8, 1 -> 9, 2 -> 10, 2 -> 11, 3 -> 4, 3 -> 5, 3 -> 8, 3 -> 10, 4 -> 6, 4 -> 8, 4 -> 11, 5 -> 6, 5 -> 9, 5 -> 10, 6 -> 9, 6 -> 11, 7 -> 8, 7 -> 9, 7 -> 10, 7 -> 11, 8 -> 9, 10 -> 11}}
    
18. {11, 23, ">>graph6<<J`GhcpJdQL_", {1 -> 2, 1 -> 8, 1 -> 10, 2 -> 9, 2 -> 11, 3 -> 4, 3 -> 5, 3 -> 6, 3 -> 7, 4 -> 7, 4 -> 8, 4 -> 10, 5 -> 6, 5 -> 8, 5 -> 9, 6 -> 10, 6 -> 11, 7 -> 9, 7 -> 11, 8 -> 9, 8 -> 10, 9 -> 11, 10 -> 11}}
    
19. {12, 27, ">>graph6<<KwC[KLQIibDJ", {1 -> 2, 1 -> 3, 1 -> 7, 1 -> 8, 2 -> 3, 2 -> 9, 2 -> 11, 3 -> 10, 3 -> 12, 4 -> 5, 4 -> 6, 4 -> 9, 4 -> 11, 5 -> 6, 5 -> 10, 5 -> 12, 6 -> 7, 6 -> 8, 7 -> 8, 7 -> 9, 7 -> 10, 8 -> 11, 8 -> 12, 9 -> 10, 9 -> 11, 10 -> 12, 11 -> 12}}
    
20. {13, 30, ">>graph6<<L@rLaDBIOidEDJ", {1 -> 5, 1 -> 6, 1 -> 7, 2 -> 5, 2 -> 6, 2 -> 8, 2 -> 9, 3 -> 4, 3 -> 7, 3 -> 10, 3 -> 12, 4 -> 7, 4 -> 11, 4 -> 13, 5 -> 6, 5 -> 10, 5 -> 12, 6 -> 11, 6 -> 13, 7 -> 8, 7 -> 9, 8 -> 9, 8 -> 10, 8 -> 11, 9 -> 12, 9 -> 13, 10 -> 11, 10 -> 12, 11 -> 13, 12 -> 13}}
    
21. {14, 33, ">>graph6<<M_C_?FBNLcTHTaRP_", {1 -> 2, 1 -> 9, 1 -> 11, 1 -> 12, 2 -> 9, 2 -> 13, 2 -> 14, 3 -> 6, 3 -> 10, 3 -> 11, 3 -> 12, 4 -> 5, 4 -> 10, 4 -> 11, 4 -> 13, 5 -> 10, 5 -> 12, 5 -> 14, 6 -> 10, 6 -> 13, 6 -> 14, 7 -> 8, 7 -> 9, 7 -> 11, 7 -> 13, 8 -> 9, 8 -> 12, 8 -> 14, 9 -> 10, 11 -> 12, 11 -> 13, 12 -> 14, 13 -> 14}}
    
22. {14, 33, ">>graph6<<M_DbIo`GWg`RdIah_", {1 -> 2, 1 -> 13, 1 -> 14, 2 -> 6, 2 -> 7, 2 -> 8, 3 -> 6, 3 -> 7, 3 -> 9, 3 -> 10, 4 -> 5, 4 -> 8, 4 -> 11, 4 -> 13, 5 -> 8, 5 -> 12, 5 -> 14, 6 -> 7, 6 -> 11, 6 -> 13, 7 -> 12, 7 -> 14, 8 -> 9, 8 -> 10, 9 -> 10, 9 -> 13, 9 -> 14, 10 -> 11, 10 -> 12, 11 -> 12, 11 -> 13, 12 -> 14, 13 -> 14}}
    
23. {15, 37, ">>graph6<<NGECKA@WW{igRHKpDSW", {1 -> 6, 1 -> 7, 1 -> 8, 1 -> 9, 2 -> 3, 2 -> 10, 2 -> 12, 2 -> 13, 3 -> 10, 3 -> 14, 3 -> 15, 4 -> 5, 4 -> 11, 4 -> 12, 4 -> 14, 5 -> 11, 5 -> 13, 5 -> 15, 6 -> 7, 6 -> 11, 6 -> 12, 6 -> 13, 7 -> 11, 7 -> 14, 7 -> 15, 8 -> 9, 8 -> 10, 8 -> 12, 8 -> 14, 9 -> 10, 9 -> 13, 9 -> 15, 10 -> 11, 12 -> 13, 12 -> 14, 13 -> 15, 14 -> 15}}
    
24. {16, 41, ">>graph6<<O@iib@`cC_iOAsAi_ioHZ", {1 -> 5, 1 -> 6, 1 -> 10, 1 -> 11, 2 -> 7, 2 -> 8, 2 -> 9, 2 -> 12, 3 -> 4, 3 -> 5, 3 -> 6, 3 -> 8, 3 -> 9, 4 -> 7, 4 -> 10, 4 -> 11, 4 -> 12, 5 -> 6, 5 -> 13, 5 -> 14, 6 -> 15, 6 -> 16, 7 -> 12, 7 -> 13, 7 -> 14, 8 -> 9, 8 -> 13, 8 -> 15, 9 -> 14, 9 -> 16, 10 -> 11, 10 -> 13, 10 -> 15, 11 -> 14, 11 -> 16, 12 -> 15, 12 -> 16, 13 -> 14, 13 -> 15, 14 -> 16, 15 -> 16}}
    
25. {17, 43, ">>graph6<<P?CpiPHS@OYAiA@S_UWIY?jK", {1 -> 12, 1 -> 13, 2 -> 8, 2 -> 9, 2 -> 10, 2 -> 12, 3 -> 6, 3 -> 7, 3 -> 11, 3 -> 13, 4 -> 5, 4 -> 6, 4 -> 7, 4 -> 10, 4 -> 12, 5 -> 8, 5 -> 9, 5 -> 11, 5 -> 13, 6 -> 7, 6 -> 14, 6 -> 16, 7 -> 15, 7 -> 17, 8 -> 9, 8 -> 14, 8 -> 16, 9 -> 15, 9 -> 17, 10 -> 12, 10 -> 14, 10 -> 15, 11 -> 13, 11 -> 16, 11 -> 17, 12 -> 16, 12 -> 17, 13 -> 14, 13 -> 15, 14 -> 15, 14 -> 16, 15 -> 17, 16 -> 17}}
    
26. {17, 43, ">>graph6<<P@Oa@GoQ?d@j@KEoWPOFef?w", {1 -> 15, 1 -> 17, 2 -> 5, 2 -> 7, 2 -> 10, 2 -> 15, 3 -> 4, 3 -> 6, 3 -> 8, 3 -> 9, 4 -> 9, 4 -> 11, 4 -> 14, 4 -> 17, 5 -> 10, 5 -> 12, 5 -> 14, 5 -> 17, 6 -> 8, 6 -> 12, 6 -> 13, 6 -> 17, 7 -> 11, 7 -> 14, 7 -> 15, 7 -> 16, 8 -> 12, 8 -> 14, 8 -> 16, 9 -> 11, 9 -> 13, 9 -> 16, 10 -> 12, 10 -> 13, 10 -> 16, 11 -> 12, 11 -> 15, 13 -> 15, 13 -> 16, 13 -> 17, 14 -> 16, 14 -> 17, 15 -> 17}}
    
27. {17, 43, ">>graph6<<P?_YQT_K@_r_wG@c_hWDi?ZK", {1 -> 5, 1 -> 12, 1 -> 13, 2 -> 7, 2 -> 8, 2 -> 9, 2 -> 13, 3 -> 9, 3 -> 10, 3 -> 11, 3 -> 13, 4 -> 6, 4 -> 10, 4 -> 11, 4 -> 12, 5 -> 6, 5 -> 7, 5 -> 8, 5 -> 12, 6 -> 12, 6 -> 14, 6 -> 15, 7 -> 8, 7 -> 14, 7 -> 16, 8 -> 15, 8 -> 17, 9 -> 13, 9 -> 16, 9 -> 17, 10 -> 11, 10 -> 14, 10 -> 16, 11 -> 15, 11 -> 17, 12 -> 16, 12 -> 17, 13 -> 14, 13 -> 15, 14 -> 15, 14 -> 16, 15 -> 17, 16 -> 17}}
    
28. {17, 43, ">>graph6<<P?O`H`OSHaRoq@@I_RWZAAsK", {1 -> 12, 1 -> 13, 2 -> 5, 2 -> 9, 2 -> 10, 2 -> 13, 3 -> 6, 3 -> 7, 3 -> 8, 3 -> 11, 4 -> 8, 4 -> 9, 4 -> 10, 4 -> 11, 4 -> 12, 5 -> 12, 5 -> 13, 5 -> 16, 5 -> 17, 6 -> 7, 6 -> 12, 6 -> 14, 6 -> 16, 7 -> 12, 7 -> 15, 7 -> 17, 8 -> 11, 8 -> 16, 8 -> 17, 9 -> 10, 9 -> 14, 9 -> 16, 10 -> 15, 10 -> 17, 11 -> 14, 11 -> 15, 12 -> 13, 13 -> 14, 13 -> 15, 14 -> 15, 14 -> 16, 15 -> 17, 16 -> 17}}
    
29. {17, 43, ">>graph6<<P?SaACcK@_q{u??k_LW[aBQK", {1 -> 12, 1 -> 13, 2 -> 5, 2 -> 7, 2 -> 8, 2 -> 13, 3 -> 6, 3 -> 9, 3 -> 10, 3 -> 11, 4 -> 5, 4 -> 10, 4 -> 11, 4 -> 12, 4 -> 13, 5 -> 13, 5 -> 16, 5 -> 17, 6 -> 9, 6 -> 12, 6 -> 16, 6 -> 17, 7 -> 8, 7 -> 12, 7 -> 14, 7 -> 16, 8 -> 12, 8 -> 15, 8 -> 17, 9 -> 12, 9 -> 14, 9 -> 15, 10 -> 11, 10 -> 14, 10 -> 16, 11 -> 15, 11 -> 17, 13 -> 14, 13 -> 15, 14 -> 15, 14 -> 16, 15 -> 17, 16 -> 17}}
    
30. {17, 43, ">>graph6<<PJPK?CA?gYEF_qEGaaXRAHSK", {1 -> 7, 1 -> 13, 2 -> 3, 2 -> 4, 2 -> 5, 2 -> 6, 3 -> 4, 3 -> 12, 3 -> 16, 3 -> 17, 4 -> 12, 4 -> 14, 4 -> 15, 5 -> 6, 5 -> 11, 5 -> 14, 5 -> 16, 6 -> 11, 6 -> 15, 6 -> 17, 7 -> 8, 7 -> 9, 7 -> 10, 7 -> 13, 8 -> 11, 8 -> 13, 8 -> 16, 8 -> 17, 9 -> 10, 9 -> 12, 9 -> 14, 9 -> 16, 10 -> 12, 10 -> 15, 10 -> 17, 11 -> 12, 11 -> 13, 13 -> 14, 13 -> 15, 14 -> 15, 14 -> 16, 15 -> 17, 16 -> 17}}
    
31. {17, 43, ">>graph6<<PASaACcG@?rB`xDcAhGTaAYK", {1 -> 12, 1 -> 13, 2 -> 4, 2 -> 5, 2 -> 7, 2 -> 8, 3 -> 6, 3 -> 9, 3 -> 10, 3 -> 11, 4 -> 5, 4 -> 12, 4 -> 14, 4 -> 15, 5 -> 12, 5 -> 16, 5 -> 17, 6 -> 9, 6 -> 13, 6 -> 14, 6 -> 15, 7 -> 8, 7 -> 13, 7 -> 14, 7 -> 16, 8 -> 13, 8 -> 15, 8 -> 17, 9 -> 13, 9 -> 16, 9 -> 17, 10 -> 11, 10 -> 12, 10 -> 14, 10 -> 16, 11 -> 12, 11 -> 15, 11 -> 17, 12 -> 13, 14 -> 15, 14 -> 16, 15 -> 17, 16 -> 17}}
    
32. {18, 46, ">>graph6<<Q_HG_gT_`?cB?q?hiQ?QTAH^kB?", {1 -> 2, 1 -> 10, 1 -> 18, 2 -> 6, 2 -> 15, 2 -> 18, 3 -> 5, 3 -> 11, 3 -> 12, 3 -> 18, 4 -> 7, 4 -> 8, 4 -> 9, 4 -> 15, 5 -> 6, 5 -> 16, 5 -> 17, 5 -> 18, 6 -> 8, 6 -> 9, 6 -> 18, 7 -> 10, 7 -> 13, 7 -> 14, 7 -> 15, 8 -> 9, 8 -> 13, 8 -> 16, 9 -> 14, 9 -> 17, 10 -> 11, 10 -> 12, 10 -> 15, 11 -> 12, 11 -> 13, 11 -> 16, 12 -> 14, 12 -> 17, 13 -> 14, 13 -> 16, 13 -> 18, 14 -> 17, 14 -> 18, 15 -> 16, 15 -> 17, 16 -> 17}}
    
33. {18, 46, ">>graph6<<Q`G@O?oDII@YAWD_OHiGs@wqWBo", {1 -> 2, 1 -> 15, 1 -> 18, 2 -> 11, 2 -> 16, 3 -> 4, 3 -> 5, 3 -> 7, 3 -> 9, 4 -> 9, 4 -> 10, 4 -> 14, 4 -> 18, 5 -> 7, 5 -> 12, 5 -> 13, 5 -> 18, 6 -> 10, 6 -> 11, 6 -> 14, 6 -> 16, 6 -> 17, 7 -> 12, 7 -> 14, 7 -> 17, 8 -> 11, 8 -> 12, 8 -> 13, 8 -> 15, 8 -> 17, 9 -> 10, 9 -> 13, 9 -> 17, 10 -> 12, 10 -> 16, 11 -> 15, 11 -> 16, 12 -> 15, 13 -> 16, 13 -> 17, 13 -> 18, 14 -> 15, 14 -> 17, 14 -> 18, 15 -> 18, 16 -> 18}}
    
34. {18, 46, ">>graph6<<Q?CX@C_CAXOYAg@W`QOIbwINOV?", {1 -> 12, 1 -> 17, 1 -> 18, 2 -> 11, 2 -> 17, 2 -> 18, 3 -> 7, 3 -> 8, 3 -> 9, 3 -> 17, 4 -> 5, 4 -> 6, 4 -> 10, 4 -> 18, 5 -> 6, 5 -> 11, 5 -> 13, 5 -> 15, 6 -> 11, 6 -> 14, 6 -> 16, 7 -> 8, 7 -> 12, 7 -> 13, 7 -> 15, 8 -> 12, 8 -> 14, 8 -> 16, 9 -> 11, 9 -> 13, 9 -> 14, 9 -> 17, 10 -> 12, 10 -> 15, 10 -> 16, 10 -> 18, 11 -> 17, 12 -> 18, 13 -> 14, 13 -> 15, 13 -> 18, 14 -> 16, 14 -> 18, 15 -> 16, 15 -> 17, 16 -> 17}}
    
35. {18, 46, ">>graph6<<Q_GP@COCGC_LBeBXgwCP`iBDSK_", {1 -> 2, 1 -> 16, 1 -> 17, 2 -> 15, 2 -> 18, 3 -> 5, 3 -> 7, 3 -> 8, 3 -> 17, 4 -> 6, 4 -> 9, 4 -> 10, 4 -> 18, 5 -> 13, 5 -> 14, 5 -> 16, 5 -> 17, 6 -> 13, 6 -> 14, 6 -> 15, 6 -> 18, 7 -> 8, 7 -> 11, 7 -> 13, 7 -> 15, 8 -> 12, 8 -> 14, 8 -> 15, 9 -> 10, 9 -> 12, 9 -> 14, 9 -> 16, 10 -> 11, 10 -> 13, 10 -> 16, 11 -> 12, 11 -> 13, 11 -> 17, 11 -> 18, 12 -> 14, 12 -> 17, 12 -> 18, 13 -> 14, 15 -> 16, 15 -> 18, 16 -> 17}}
    
36. {18, 46, ">>graph6<<Q?GP?aHP_K?hAaAPtDbCidCpPi?", {1 -> 9, 1 -> 15, 1 -> 17, 2 -> 10, 2 -> 16, 2 -> 18, 3 -> 5, 3 -> 7, 3 -> 15, 3 -> 16, 4 -> 6, 4 -> 8, 4 -> 17, 4 -> 18, 5 -> 9, 5 -> 13, 5 -> 14, 5 -> 15, 6 -> 10, 6 -> 11, 6 -> 12, 6 -> 17, 7 -> 10, 7 -> 11, 7 -> 13, 7 -> 16, 8 -> 9, 8 -> 12, 8 -> 14, 8 -> 18, 9 -> 15, 9 -> 18, 10 -> 16, 10 -> 17, 11 -> 12, 11 -> 13, 11 -> 15, 11 -> 18, 12 -> 14, 12 -> 15, 12 -> 16, 13 -> 14, 13 -> 17, 13 -> 18, 14 -> 16, 14 -> 17}}
    
37. {18, 46, ">>graph6<<Q_GP?ggC?ZIA@KApSOQCx?{qKF_", {1 -> 2, 1 -> 15, 1 -> 18, 2 -> 12, 2 -> 16, 3 -> 5, 3 -> 7, 3 -> 9, 3 -> 15, 4 -> 6, 4 -> 8, 4 -> 10, 4 -> 12, 5 -> 9, 5 -> 11, 5 -> 14, 5 -> 18, 6 -> 8, 6 -> 11, 6 -> 13, 6 -> 18, 7 -> 14, 7 -> 15, 7 -> 16, 7 -> 17, 8 -> 11, 8 -> 14, 8 -> 17, 9 -> 11, 9 -> 13, 9 -> 17, 10 -> 12, 10 -> 13, 10 -> 16, 10 -> 17, 11 -> 16, 12 -> 14, 12 -> 16, 12 -> 18, 13 -> 15, 13 -> 17, 13 -> 18, 14 -> 17, 14 -> 18, 15 -> 16, 15 -> 18}}
    
38. {18, 46, ">>graph6<<Q_?oq?`APgPIWW?e_cas@?M]EF_", {1 -> 2, 1 -> 12, 1 -> 18, 2 -> 8, 2 -> 13, 2 -> 16, 3 -> 6, 3 -> 9, 3 -> 11, 3 -> 13, 4 -> 6, 4 -> 7, 4 -> 11, 4 -> 16, 5 -> 7, 5 -> 10, 5 -> 12, 5 -> 16, 6 -> 11, 6 -> 15, 6 -> 18, 7 -> 14, 7 -> 16, 7 -> 18, 8 -> 9, 8 -> 10, 8 -> 12, 8 -> 13, 9 -> 13, 9 -> 15, 9 -> 17, 10 -> 12, 10 -> 14, 10 -> 17, 11 -> 14, 11 -> 17, 12 -> 15, 12 -> 18, 13 -> 14, 13 -> 18, 14 -> 17, 14 -> 18, 15 -> 16, 15 -> 17, 15 -> 18, 16 -> 17}}
    
39. {18, 46, ">>graph6<<Q_?HGoSDHKBG?J?Ft?ROB_whBPW", {1 -> 2, 1 -> 15, 1 -> 17, 2 -> 16, 2 -> 18, 3 -> 7, 3 -> 11, 3 -> 15, 3 -> 16, 4 -> 8, 4 -> 9, 4 -> 10, 4 -> 12, 5 -> 6, 5 -> 8, 5 -> 12, 5 -> 15, 5 -> 16, 6 -> 7, 6 -> 9, 6 -> 10, 6 -> 11, 7 -> 11, 7 -> 17, 7 -> 18, 8 -> 12, 8 -> 17, 8 -> 18, 9 -> 10, 9 -> 13, 9 -> 17, 10 -> 14, 10 -> 18, 11 -> 13, 11 -> 14, 12 -> 13, 12 -> 14, 13 -> 14, 13 -> 15, 13 -> 17, 14 -> 16, 14 -> 18, 15 -> 16, 15 -> 17, 16 -> 18, 17 -> 18}}
    
40. {18, 46, ">>graph6<<Q_?HPGdI_oA_?N?oQ_ioQ_ix@VO", {1 -> 2, 1 -> 15, 1 -> 17, 2 -> 16, 2 -> 18, 3 -> 7, 3 -> 8, 3 -> 9, 3 -> 10, 4 -> 11, 4 -> 12, 4 -> 15, 4 -> 16, 5 -> 6, 5 -> 7, 5 -> 10, 5 -> 11, 5 -> 16, 6 -> 8, 6 -> 9, 6 -> 12, 6 -> 15, 7 -> 10, 7 -> 14, 7 -> 17, 8 -> 9, 8 -> 14, 8 -> 18, 9 -> 13, 9 -> 17, 10 -> 13, 10 -> 18, 11 -> 13, 11 -> 16, 11 -> 17, 12 -> 13, 12 -> 15, 12 -> 18, 13 -> 17, 13 -> 18, 14 -> 15, 14 -> 16, 14 -> 17, 14 -> 18, 15 -> 17, 16 -> 18}}
    
41. {18, 46, ">>graph6<<Q_?P@CgE?oi_?d?R_uOJRiGrNC?", {1 -> 2, 1 -> 17, 1 -> 18, 2 -> 12, 2 -> 18, 3 -> 7, 3 -> 8, 3 -> 9, 3 -> 17, 4 -> 6, 4 -> 10, 4 -> 11, 4 -> 12, 5 -> 9, 5 -> 10, 5 -> 11, 5 -> 17, 5 -> 18, 6 -> 12, 6 -> 15, 6 -> 16, 6 -> 18, 7 -> 8, 7 -> 13, 7 -> 15, 7 -> 18, 8 -> 14, 8 -> 16, 8 -> 18, 9 -> 15, 9 -> 16, 9 -> 17, 10 -> 11, 10 -> 13, 10 -> 15, 11 -> 14, 11 -> 16, 12 -> 13, 12 -> 14, 12 -> 18, 13 -> 14, 13 -> 15, 13 -> 17, 14 -> 16, 14 -> 17, 15 -> 16}}
    
42. {18, 46, ">>graph6<<Q_?Oh?`E?o_i?t@J?TZOIi?nN_?", {1 -> 2, 1 -> 17, 1 -> 18, 2 -> 16, 2 -> 18, 3 -> 8, 3 -> 9, 3 -> 16, 3 -> 17, 4 -> 6, 4 -> 7, 4 -> 10, 4 -> 11, 5 -> 10, 5 -> 11, 5 -> 16, 5 -> 17, 5 -> 18, 6 -> 7, 6 -> 12, 6 -> 14, 6 -> 18, 7 -> 13, 7 -> 15, 7 -> 18, 8 -> 9, 8 -> 12, 8 -> 13, 8 -> 18, 9 -> 14, 9 -> 15, 9 -> 18, 10 -> 11, 10 -> 12, 10 -> 13, 11 -> 14, 11 -> 15, 12 -> 13, 12 -> 14, 12 -> 16, 13 -> 15, 13 -> 17, 14 -> 15, 14 -> 16, 15 -> 17, 16 -> 17}}
    
43. {18, 46, ">>graph6<<QGCCIGdX?oq?c@?r?T[K_QPSgaw", {1 -> 7, 1 -> 12, 1 -> 13, 1 -> 16, 2 -> 3, 2 -> 8, 2 -> 10, 2 -> 17, 3 -> 9, 3 -> 10, 3 -> 18, 4 -> 5, 4 -> 11, 4 -> 12, 4 -> 13, 5 -> 11, 5 -> 17, 5 -> 18, 6 -> 7, 6 -> 8, 6 -> 9, 6 -> 10, 6 -> 16, 7 -> 14, 7 -> 15, 7 -> 16, 8 -> 9, 8 -> 14, 8 -> 17, 9 -> 15, 9 -> 18, 10 -> 11, 10 -> 16, 11 -> 14, 11 -> 15, 12 -> 13, 12 -> 14, 12 -> 17, 13 -> 15, 13 -> 18, 14 -> 15, 14 -> 17, 15 -> 18, 16 -> 17, 16 -> 18, 17 -> 18}}
    
44. {18, 46, ">>graph6<<Q??OP_g?WI_U@bdDHRBaKiIbE@_", {1 -> 14, 1 -> 17, 1 -> 18, 2 -> 15, 2 -> 16, 2 -> 18, 3 -> 8, 3 -> 9, 3 -> 16, 3 -> 17, 4 -> 6, 4 -> 8, 4 -> 14, 4 -> 16, 5 -> 7, 5 -> 9, 5 -> 15, 5 -> 17, 6 -> 11, 6 -> 13, 6 -> 14, 6 -> 18, 7 -> 12, 7 -> 13, 7 -> 15, 7 -> 18, 8 -> 10, 8 -> 11, 8 -> 16, 9 -> 10, 9 -> 12, 9 -> 17, 10 -> 11, 10 -> 12, 10 -> 14, 10 -> 15, 11 -> 13, 11 -> 15, 11 -> 17, 12 -> 13, 12 -> 14, 12 -> 16, 13 -> 16, 13 -> 17, 14 -> 18, 15 -> 18}}
    
45. {18, 46, ">>graph6<<Qw?G@_K?gDoOO`EBA`XbKaTPDQg", {1 -> 2, 1 -> 3, 1 -> 12, 1 -> 17, 2 -> 3, 2 -> 13, 2 -> 18, 3 -> 8, 3 -> 16, 4 -> 8, 4 -> 14, 4 -> 15, 4 -> 16, 5 -> 6, 5 -> 9, 5 -> 14, 5 -> 17, 6 -> 9, 6 -> 15, 6 -> 18, 7 -> 10, 7 -> 11, 7 -> 12, 7 -> 13, 8 -> 16, 8 -> 17, 8 -> 18, 9 -> 10, 9 -> 11, 9 -> 16, 10 -> 11, 10 -> 17, 10 -> 18, 11 -> 14, 11 -> 15, 12 -> 13, 12 -> 14, 12 -> 16, 12 -> 17, 13 -> 15, 13 -> 16, 13 -> 18, 14 -> 15, 14 -> 17, 15 -> 18, 17 -> 18}}
    
46. {18, 46, ">>graph6<<QKc?G_HW?G_b`_GqCSkFcSQpGeg", {1 -> 4, 1 -> 5, 1 -> 13, 1 -> 16, 2 -> 3, 2 -> 10, 2 -> 17, 2 -> 18, 3 -> 10, 3 -> 14, 3 -> 15, 4 -> 5, 4 -> 8, 4 -> 17, 5 -> 9, 5 -> 18, 6 -> 7, 6 -> 11, 6 -> 12, 6 -> 13, 7 -> 13, 7 -> 14, 7 -> 15, 7 -> 16, 8 -> 9, 8 -> 14, 8 -> 16, 8 -> 17, 9 -> 15, 9 -> 16, 9 -> 18, 10 -> 11, 10 -> 12, 10 -> 16, 11 -> 12, 11 -> 14, 11 -> 17, 12 -> 15, 12 -> 18, 13 -> 16, 13 -> 17, 13 -> 18, 14 -> 15, 14 -> 17, 15 -> 18, 17 -> 18}}
    
47. {18, 46, ">>graph6<<QwC?H?W@gA``Ab_XGKXAod@TQAw", {1 -> 2, 1 -> 3, 1 -> 14, 1 -> 17, 2 -> 3, 2 -> 15, 2 -> 18, 3 -> 8, 3 -> 16, 4 -> 5, 4 -> 9, 4 -> 17, 4 -> 18, 5 -> 9, 5 -> 12, 5 -> 13, 6 -> 7, 6 -> 10, 6 -> 12, 6 -> 17, 7 -> 10, 7 -> 13, 7 -> 18, 8 -> 11, 8 -> 14, 8 -> 15, 8 -> 16, 9 -> 10, 9 -> 14, 9 -> 15, 10 -> 11, 10 -> 16, 11 -> 12, 11 -> 13, 11 -> 16, 12 -> 13, 12 -> 14, 12 -> 17, 13 -> 15, 13 -> 18, 14 -> 15, 14 -> 17, 15 -> 18, 16 -> 17, 16 -> 18, 17 -> 18}}
    
48. {19, 50, ">>graph6<<RJ?GKEB`CGh?AKAIh_`CKC`S`QoaRW", {1 -> 8, 1 -> 9, 1 -> 10, 1 -> 11, 2 -> 3, 2 -> 4, 2 -> 12, 2 -> 15, 3 -> 4, 3 -> 16, 3 -> 18, 4 -> 17, 4 -> 19, 5 -> 6, 5 -> 12, 5 -> 13, 5 -> 14, 5 -> 15, 6 -> 7, 6 -> 10, 6 -> 11, 6 -> 15, 7 -> 8, 7 -> 9, 7 -> 16, 7 -> 17, 8 -> 9, 8 -> 18, 8 -> 19, 9 -> 13, 9 -> 14, 10 -> 11, 10 -> 13, 10 -> 18, 11 -> 14, 11 -> 19, 12 -> 15, 12 -> 16, 12 -> 17, 13 -> 14, 13 -> 16, 13 -> 18, 14 -> 17, 14 -> 19, 15 -> 18, 15 -> 19, 16 -> 17, 16 -> 18, 17 -> 19, 18 -> 19}}
    
49. {19, 50, ">>graph6<<R@KCAHD`CG_U?jH_SOI_IQ?sPSoQTW", {1 -> 7, 1 -> 10, 1 -> 11, 1 -> 15, 2 -> 8, 2 -> 9, 2 -> 16, 2 -> 17, 3 -> 4, 3 -> 5, 3 -> 14, 3 -> 15, 4 -> 5, 4 -> 16, 4 -> 18, 5 -> 17, 5 -> 19, 6 -> 8, 6 -> 9, 6 -> 10, 6 -> 11, 6 -> 14, 7 -> 12, 7 -> 13, 7 -> 14, 7 -> 15, 8 -> 9, 8 -> 18, 8 -> 19, 9 -> 12, 9 -> 13, 10 -> 11, 10 -> 12, 10 -> 18, 11 -> 13, 11 -> 19, 12 -> 13, 12 -> 16, 12 -> 18, 13 -> 17, 13 -> 19, 14 -> 15, 14 -> 16, 14 -> 17, 15 -> 18, 15 -> 19, 16 -> 17, 16 -> 18, 17 -> 19, 18 -> 19}}
    
50. {19, 50, ">>graph6<<R?CCGx_oE?_Q?b`oKKpgGJ?cOtOPUW", {1 -> 7, 1 -> 10, 1 -> 11, 1 -> 14, 2 -> 9, 2 -> 10, 2 -> 11, 2 -> 15, 3 -> 9, 3 -> 15, 3 -> 16, 3 -> 17, 4 -> 5, 4 -> 8, 4 -> 16, 4 -> 18, 5 -> 8, 5 -> 17, 5 -> 19, 6 -> 7, 6 -> 8, 6 -> 14, 6 -> 16, 6 -> 17, 7 -> 12, 7 -> 13, 7 -> 14, 8 -> 14, 8 -> 15, 9 -> 15, 9 -> 18, 9 -> 19, 10 -> 11, 10 -> 12, 10 -> 18, 11 -> 13, 11 -> 19, 12 -> 13, 12 -> 15, 12 -> 16, 12 -> 18, 13 -> 15, 13 -> 17, 13 -> 19, 14 -> 18, 14 -> 19, 16 -> 17, 16 -> 18, 17 -> 19, 18 -> 19}}
    
51. {20, 54, ">>graph6<<S?E@cQHWB?_Q?bDPAcYWKM_BC?OAiW@T[", {1 -> 6, 1 -> 8, 1 -> 9, 1 -> 18, 2 -> 10, 2 -> 11, 2 -> 16, 2 -> 18, 3 -> 7, 3 -> 10, 3 -> 11, 3 -> 17, 4 -> 5, 4 -> 7, 4 -> 14, 4 -> 15, 4 -> 17, 5 -> 8, 5 -> 9, 5 -> 16, 5 -> 17, 6 -> 14, 6 -> 15, 6 -> 16, 6 -> 18, 7 -> 12, 7 -> 13, 7 -> 17, 8 -> 9, 8 -> 14, 8 -> 19, 9 -> 15, 9 -> 20, 10 -> 11, 10 -> 12, 10 -> 19, 11 -> 13, 11 -> 20, 12 -> 13, 12 -> 14, 12 -> 16, 12 -> 19, 13 -> 15, 13 -> 16, 13 -> 20, 14 -> 15, 14 -> 19, 15 -> 20, 16 -> 18, 17 -> 19, 17 -> 20, 18 -> 19, 18 -> 20, 19 -> 20}}
    
52. {21, 57, ">>graph6<<Tsc@IGC@GD?R?S?Wd@A_CK@HG@VM??PRKOUZ", {1 -> 2, 1 -> 3, 1 -> 4, 1 -> 5, 1 -> 19, 2 -> 8, 2 -> 16, 2 -> 18, 2 -> 19, 3 -> 7, 3 -> 15, 3 -> 17, 3 -> 19, 4 -> 5, 4 -> 16, 4 -> 17, 4 -> 21, 5 -> 15, 5 -> 18, 5 -> 20, 6 -> 7, 6 -> 8, 6 -> 9, 6 -> 10, 6 -> 19, 7 -> 11, 7 -> 12, 7 -> 19, 8 -> 13, 8 -> 14, 8 -> 19, 9 -> 10, 9 -> 11, 9 -> 14, 9 -> 20, 10 -> 12, 10 -> 13, 10 -> 21, 11 -> 12, 11 -> 15, 11 -> 20, 12 -> 17, 12 -> 21, 13 -> 14, 13 -> 16, 13 -> 21, 14 -> 18, 14 -> 20, 15 -> 17, 15 -> 20, 16 -> 18, 16 -> 21, 17 -> 21, 18 -> 20, 19 -> 20, 19 -> 21, 20 -> 21}}
    
53. {21, 57, ">>graph6<<TCKx?D?OI?OMCBSA_L?ApA_gEA\\EG?PBSCPV", {1 -> 4, 1 -> 12, 1 -> 19, 2 -> 9, 2 -> 10, 2 -> 11, 2 -> 14, 3 -> 5, 3 -> 6, 3 -> 7, 3 -> 19, 4 -> 5, 4 -> 6, 4 -> 13, 4 -> 14, 5 -> 6, 5 -> 17, 5 -> 20, 6 -> 18, 6 -> 21, 7 -> 8, 7 -> 17, 7 -> 18, 7 -> 19, 8 -> 12, 8 -> 15, 8 -> 16, 8 -> 19, 9 -> 10, 9 -> 12, 9 -> 15, 9 -> 20, 10 -> 12, 10 -> 16, 10 -> 21, 11 -> 13, 11 -> 14, 11 -> 15, 11 -> 16, 12 -> 13, 12 -> 19, 13 -> 14, 13 -> 17, 13 -> 18, 14 -> 20, 14 -> 21, 15 -> 16, 15 -> 17, 15 -> 20, 16 -> 18, 16 -> 21, 17 -> 18, 17 -> 20, 18 -> 21, 19 -> 20, 19 -> 21, 20 -> 21}}
    
54. {21, 57, ">>graph6<<TCTWACAG@@CDKC?e?QgQA@OMOq]F??OUcCEj", {1 -> 4, 1 -> 18, 1 -> 19, 2 -> 5, 2 -> 6, 2 -> 8, 2 -> 19, 3 -> 10, 3 -> 11, 3 -> 12, 3 -> 13, 4 -> 5, 4 -> 6, 4 -> 13, 4 -> 18, 5 -> 6, 5 -> 16, 5 -> 20, 6 -> 17, 6 -> 21, 7 -> 8, 7 -> 9, 7 -> 14, 7 -> 15, 7 -> 19, 8 -> 16, 8 -> 17, 8 -> 19, 9 -> 11, 9 -> 12, 9 -> 18, 9 -> 19, 10 -> 13, 10 -> 14, 10 -> 15, 10 -> 18, 11 -> 12, 11 -> 14, 11 -> 20, 12 -> 15, 12 -> 21, 13 -> 18, 13 -> 20, 13 -> 21, 14 -> 15, 14 -> 16, 14 -> 20, 15 -> 17, 15 -> 21, 16 -> 17, 16 -> 18, 16 -> 20, 17 -> 18, 17 -> 21, 19 -> 20, 19 -> 21, 20 -> 21}}
    
55. {21, 57, ">>graph6<<TCS`?H??XIZ?K_Co`CG@JO[?EOSCpGOTSCE\", {1 -> 4, 1 -> 12, 1 -> 19, 2 -> 5, 2 -> 9, 2 -> 12, 2 -> 17, 3 -> 6, 3 -> 7, 3 -> 11, 3 -> 13, 4 -> 5, 4 -> 12, 4 -> 13, 4 -> 14, 5 -> 12, 5 -> 15, 5 -> 20, 6 -> 8, 6 -> 11, 6 -> 18, 6 -> 21, 7 -> 13, 7 -> 14, 7 -> 18, 7 -> 19, 8 -> 10, 8 -> 11, 8 -> 14, 8 -> 17, 9 -> 10, 9 -> 15, 9 -> 16, 9 -> 17, 10 -> 17, 10 -> 18, 10 -> 19, 11 -> 19, 11 -> 20, 12 -> 16, 12 -> 21, 13 -> 14, 13 -> 20, 13 -> 21, 14 -> 15, 14 -> 16, 15 -> 16, 15 -> 19, 15 -> 20, 16 -> 18, 16 -> 21, 17 -> 20, 17 -> 21, 18 -> 19, 18 -> 21, 19 -> 20, 20 -> 21}}
    
56. {21, 57, ">>graph6<<T??_`OhSCSYA@I?c?OyWBEa@c?SIU?Aa[?el", {1 -> 11, 1 -> 12, 1 -> 19, 2 -> 10, 2 -> 12, 2 -> 16, 2 -> 18, 3 -> 6, 3 -> 8, 3 -> 9, 3 -> 18, 4 -> 7, 4 -> 10, 4 -> 12, 4 -> 17, 5 -> 8, 5 -> 9, 5 -> 11, 5 -> 16, 5 -> 17, 6 -> 13, 6 -> 16, 6 -> 18, 6 -> 19, 7 -> 11, 7 -> 14, 7 -> 15, 7 -> 17, 8 -> 9, 8 -> 19, 8 -> 20, 9 -> 13, 9 -> 21, 10 -> 12, 10 -> 14, 10 -> 20, 11 -> 13, 11 -> 17, 11 -> 19, 12 -> 15, 12 -> 21, 13 -> 15, 13 -> 19, 13 -> 21, 14 -> 15, 14 -> 16, 14 -> 19, 14 -> 20, 15 -> 16, 15 -> 21, 16 -> 18, 17 -> 20, 17 -> 21, 18 -> 20, 18 -> 21, 19 -> 20, 20 -> 21}}
    

复制代码

wayne

21有个图挺不错的各个边是等长的,Mathematica画出来没有考虑等长,而光顾着对称性了

1. {1->2,1->3,1->4,1->5,1->19,2->8,2->16,2->18,2->19,3->7,3->15,3->17,3->19,4->5,4->16,4->17,4->21,5->15,5->18,5->20,6->7,6->8,6->9,6->10,6->19,7->11,7->12,7->19,8->13,8->14,8->19,9->10,9->11,9->14,9->20,10->12,10->13,10->21,11->12,11->15,11->20,12->17,12->21,13->14,13->16,13->21,14->18,14->20,15->17,15->20,16->18,16->21,17->21,18->20,19->20,19->21,20->21}

复制代码

mathe

这篇论文晦涩难懂呀。
不过这个题目感觉应该比果树问题容易。

我们可以看到，在点数增加时，候选图里面会出现大量正三角形，而每个正三角形三个顶点之间相对位置是固定了（除了平移和旋转）。
而如果两个正三角形有公共边，那么它们之间相对关系也可以确定。
所以对一个图，我们可以先找出其中所有正三角形，然后以这些正三角形为点构造另外一个图，当且仅当两个正三角形有公共边，给它们在这个图上对应点之间连边。于是我们可以知道，这个图上任何一个连通分支中的所有三角形对应的图在旋转和平移意义下是唯一的。
比如对于图\(K_4\), 四个点两两相邻，可以找到四个正三角形，它们两两有公共边（也是$K_4$), 可以先做出两个正三角形，并且求出所有顶点坐标（任意先指定两个相邻点的坐标），然后再验证第三个正三角形的时候就可以判断出有问题，于是可以淘汰\(K_4\)这个构图。

同样对于11#中非法图ABACAFBDBFCECFDEDFEF
可以看出我们可以找到SCC
(CEF)(DEF)(BDF)(ABF)(ACF),前四个三角形完全确定所有点的位置，然后我们发现接下去验证最后一个三角形ACF时，边AC长度已经不是1
可以淘汰。

而对于另外一个非法图ABACBDBFCECFDEDFEF
可以找到SCC （BDF)(DEF) (CEF), 这三个三角形完全确定了半个正六边形，其中F是中心，BC是直径，所以长度为2。
而我们还余下两条边AB,AC长度都是1，这只能要求A是BC中点，于是同F重叠，不符合条件。

mathe

所以计算一个边较多的图的所有点的坐标，可以
1)构建正三角形关系图，并且找到其所有SCC, 在每个SCC内部计算所有点的一组内部坐标（不同SCC采用不同坐标系），或者淘汰这种可能
2）对于每个SCC内部的点之间，还可能存在一些非正三角形的边，计算这些边的实际长度，如果不等于1也淘汰可能。
3）如果某个SCC外部的一点和这个SCC中至少有两个点存在边的连接，可以利用这个关系推算这个第三个点在这个SCC中的坐标的可能性。
     如果这个点和SCC中至少三个以上点存在连接关系，那么必然可以唯一确定这个点的坐标，计算其坐标值，并且将这个点加入这个SCC.
     如果这个新点和SCC正好有两个点存在连接关系，那么存在三种可能:
        这两个点距离大于2，是不可能的存在，淘汰这种可能
        这两个点距离等于2，于是这个新点是两个SCC中点的中点，计算其坐标，并且加入SCC.
        如果这两个点的距离小于2，它有两种坐标可能，如果其中两个坐标都已经被SCC中某点使用，淘汰；如果正好有一个坐标被SCC中某点使用，它必然是另外一个，将它加入SCC. 如果两个坐标都还没有被SCC中点使用，那么不做任何额外处理。
4） 如果两个不同的SCC之间存在公共点，
      那么计算这些公共点在两个SCC内部的距离，必须完全匹配，如果存在不匹配现象，淘汰。
      如果这些公共点中存在三个点不在一条直线上，那么必然可以确定一个唯一的平移和旋转翻转方案，使得两个SCC在公共点可以重合，计算这个方案，并且将两个SCC合并为一个SCC. 然后确定两SCC之间是否还存在其它额外的边连接，并且验证它们长度是否为1，如果存在长度非1，淘汰。另外再验证合并后是否存在不同的点有相同坐标，如果存在，也淘汰。
      如果这些公共点至少两点以上，并且再一条直线上，那么必然存在两种平移旋转和翻转方案，使得这条直线上的公共点可以重合。依次判断这两种方案，根据SCC之间额外连接和点之间是否有坐标重叠来判断。如果两种方案都非法，那么没有合法方案，需要淘汰。如果两种方案中有且只有一种合法，那么两个SCC也可以合并。如果两种方案都合法，那么暂时不做合并处理。
     如果两个SCC之间有且只有一个公共点，那么判断两个SCC之间是否有其它额外连接；如果没有其它额外连接，不做任何处理；如果有一个额外连接，那么同样会存在两种可能的平移旋转翻转方案，使得这个公共点之间重合，而且额外连接也匹配。然后再根据其它连接是否匹配以及是否有重叠点判断两种方案的合法性；同样如果都不合法，那么淘汰；如果正好一种合法，那么合并；如果两种方案都合法，不额外处理，保留两个SCC。

mathe

现在代码已经实现了部分功能，但是有些判断法则还没有完成，比如两个SCC只有一个公共点的情况，没有实现。但是对于点数比较少的已经有效果了，
现在筛选结果是
n=6
ADAEBDBFCECFDEDFEF
ABACADBCBECFDEDFEF
ACAEBDBFCECFDEDFEF
ADAFBEBFCDCECFDFEF
n=7
ABACAGBEBGCFCGDEDFDGEGFG
n=8
AEAFAGBEBFBHCECGCHDFDGDHEHFG
ABAEAGBFBHCECFCGDEDFDHEGFHGH
ABAEAFBGBHCDCECGDFDHEFEGFHGH
ABAEAFBGBHCDCECFDGDHEFEGFHGH
AFAGBCBDBHCECHDFDHEGEHFGFHGH
n=9
ABACADAEBCBFBGCHCIDEDFDHEGEIFGFHGIHI
n=10
ABACADAEBCBGBHCICJDEDGDIEHEJFGFHFIFJGJHI
ABACADAEBCBHBJCICJDEDHDIEFEGFGFHFJGIGJHI
ABACADAEBHBIBJCECFCIDEDGDJEHFGFHFIGHGJIJ
ABACADAEBDBIBJCECHCJDFDHEGEIFGFHFJGIGJHI
AHAIAJBGBIBJCDCECGCIDFDGDJEFEHEIFHFJGHIJ
AIAJBCBDBEBHCFCGCHDEDFDIEGEJFGFIGJHIHJIJ
ABAFAJBCBGBJCHCICJDEDFDHDJEGEIEJFGFHGIHI
ABACAJBFBHBJCGCICJDEDFDGDJEHEIEJFGFHGIHI
n=11
AGAHAKBIBJBKCFCHCJCKDEDFDGDKEFEHEIFJGIGJHIHKIJ
AGAHAKBIBJBKCDCECICKDFDJDKEFEHEIFHFJGHGIGJHKIJ
AGAHAJBFBIBKCDCECHCIDEDJDKEFEGFHFJGIGKHIHJIKJK
ABAHAJBIBKCDCECFCHDEDGDIEJEKFHFIFKGHGIGJHJIKJK
ABAHAJBIBKCDCECFCGDGDHDJEFEHEIFJFKGIGKHIHJIKJK
ABAHAIBJBKCDCECHCJDFDHDKEFEIEJFIFKGHGIGJGKHIJK
ABACADAEBFBHBKCGCHCJDEDFDJEGEKFIFJGIGKHJHKIJIK
ABACADAEBCBHBKCICJDEDFDJEGEKFGFHFJGIGKHJHKIJIK
ABACADAEBFBHBJCGCHCKDFDIDKEGEIEJFGFJGKHJHKIJIK
ABAEAGAIBFBHBICECGCHCJDFDGDHDKEFEJFKGKHJIJIKJK
ABAEAGAIBFBHBICDCECHCJDFDGDKEFEJFKGHGKHJIJIKJK
ABAEAFAIBGBHBICDCECHCJDFDGDKEFEJFKGHGKHJIJIKJK
AEAHAIAJBFBGBIBKCFCGCHCJDEDGDHDKEFEJFKGJHKIJIK
ABAIAJBEBHBKCECGCJCKDGDHDIDKEFEKFHFIFJGHGJIJIK
ABAIAJBCBGBKCECHCKDFDHDIDKEIEJEKFGFJFKGHGJHIIJ
ABAIAJBCBEBKCGCJCKDGDHDIDKEFEHEKFHFIFJGHGJIJIK
ABAIAJBCBDBKCGCICKDHDJDKEFEIEJEKFGFHFKGHGIHJIJ
AIAJAKBCBDBFBJCECGCKDGDHDIEFEHEIFIFJGIGKHJHKJK
AIAJAKBCBDBHBICDCFCJDGDKEFEGEHEIFIFJGIGKHJHKJK
AIAJAKBCBDBFBICECFCIDEDGDJEHEKFJFKGHGIGJHIHKJK
可以看出，对于较大的n，还需要继续完善一些判断法则

mathe

先弄一个简单程序，可以把部分求解结果输出，比如对于n=6,如下

1. ADAEBDBFCECFDEDFEF:
   
2.         scc0{ A(0.00000000,0.00000000) B(2.00000000,0.00000000) C(1.00000000,1.73205081) D(1.00000000,0.00000000) E(0.50000000,0.86602540) F(1.50000000,0.86602540) }
   
3. ABACADBCBECFDEDFEF:
   
4.         scc0{ A(0.00000000,0.00000000) B(1.00000000,0.00000000) C(0.50000000,0.86602540) }
   
5.         scc1{ D(0.00000000,0.00000000) E(1.00000000,0.00000000) F(0.50000000,0.86602540) }
   
6. ACAEBDBFCECFDEDFEF:
   
7.         scc0{ A(0.00000000,0.00000000) B(2.00000000,1.73205081) C(1.00000000,0.00000000) D(1.00000000,1.73205081) E(0.50000000,0.86602540) F(1.50000000,0.86602540) }
   
8. ADAFBEBFCDCECFDFEF:
   
9.         scc0{ A(0.00000000,0.00000000) B(0.00000000,1.73205081) C(1.50000000,0.86602540) D(1.00000000,0.00000000) E(1.00000000,1.73205081) F(0.50000000,0.86602540) }
   

复制代码

需要注意，对于部分图，会找出多个scc,每个不同scc内部这时坐标是各自独立的。
可以看出，对于
ABACADBCBECFDEDFEF:
        scc0{ A(0.00000000,0.00000000) B(1.00000000,0.00000000) C(0.50000000,0.86602540) }
        scc1{ D(0.00000000,0.00000000) E(1.00000000,0.00000000) F(0.50000000,0.86602540) }
找出了两个独立SCC : ABC和DEF. 此外显然还有没被使用的边AD, BE,CF.

于是对于n=7,有
ABACAGBEBGCFCGDEDFDGEGFG:
        scc0{ A(0.00000000,0.00000000) B(1.00000000,0.00000000) C(-0.50000000,0.86602540) D(1.00000000,1.73205081) E(1.50000000,0.86602540) F(0.00000000,1.73205081) G(0.50000000,0.86602540) }

mathe

n=8的结果
AEAFAGBEBFBHCECGCHDFDGDHEHFG:
        scc0{ A(0.00000000,0.00000000) D(1.50000000,0.86602540) F(1.00000000,0.00000000) G(0.50000000,0.86602540) }
        scc1{ B(0.00000000,0.00000000) C(1.50000000,0.86602540) E(1.00000000,0.00000000) H(0.50000000,0.86602540) }
        两个SCC没有公共顶点，有四条额外跨SCC的连接AE,BF,CG,DH. (这个应该是非法解）
ABAEAGBFBHCECFCGDEDFDHEGFHGH:
        scc0{ A(0.00000000,0.00000000) C(1.50000000,0.86602540) E(1.00000000,0.00000000) G(0.50000000,0.86602540) }
        scc1{ B(0.00000000,0.00000000) D(1.50000000,0.86602540) F(1.00000000,0.00000000) H(0.50000000,0.86602540) }
        两个SCC没有公共顶点，有四条额外跨SCC的连接AB,CF,DE,GH（这个也应该是非法解）
ABAEAFBGBHCDCECGDFDHEFEGFHGH:
        scc0{ A(0.00000000,0.00000000) E(1.00000000,0.00000000) F(0.50000000,0.86602540) }
        scc1{ C(0.00000000,0.00000000) E(1.00000000,0.00000000) G(0.50000000,0.86602540) }
        scc2{ D(0.00000000,0.00000000) F(1.00000000,0.00000000) H(0.50000000,0.86602540) }
        scc3{ B(0.00000000,0.00000000) G(1.00000000,0.00000000) H(0.50000000,0.86602540) }
      四个正三角形，顶点用四条额外边连接，对应合法解，应该有额外自由度。
ABAEAFBGBHCDCECFDGDHEFEGFHGH:
        scc0{ A(0.00000000,0.00000000) C(1.50000000,0.86602540) E(1.00000000,0.00000000) F(0.50000000,0.86602540) }
        scc1{ B(0.00000000,0.00000000) D(1.50000000,0.86602540) G(1.00000000,0.00000000) H(0.50000000,0.86602540) }
        两个菱形SCC没有公共点，额外边AB,CD,EG,FH, 两条菱形对应锐角相连，两条菱形对应钝角相连，对于合法解，应该有额外自由度。
AFAGBCBDBHCECHDFDHEGEHFGFHGH:
        scc0{ A(0.00000000,0.00000000) B(2.50000000,0.86602540) C(2.00000000,1.73205081) D(2.00000000,0.00000000) E(1.00000000,1.73205081) F(1.00000000,0.00000000) G(0.50000000,0.86602540) H(1.50000000,0.86602540) }
       一个SCC,没有额外点，总是合法解。

n=9
ABACADAEBCBFBGCHCIDEDFDHEGEIFGFHGIHI:
        scc0{ A(0.00000000,0.00000000) B(1.00000000,0.00000000) C(0.50000000,0.86602540) }
        scc1{ A(0.00000000,0.00000000) D(1.00000000,0.00000000) E(0.50000000,0.86602540) }
        scc2{ B(0.00000000,0.00000000) F(1.00000000,0.00000000) G(0.50000000,0.86602540) }
        scc3{ D(0.00000000,0.00000000) F(1.00000000,0.00000000) H(0.50000000,0.86602540) }
        scc4{ E(0.00000000,0.00000000) G(1.00000000,0.00000000) I(0.50000000,0.86602540) }
        scc5{ C(0.00000000,0.00000000) H(1.00000000,0.00000000) I(0.50000000,0.86602540) }

n=10
ABACADAEBCBGBHCICJDEDGDIEHEJFGFHFIFJGJHI:
        scc0{ A(0.00000000,0.00000000) B(1.00000000,0.00000000) C(0.50000000,0.86602540) }
        scc1{ A(0.00000000,0.00000000) D(1.00000000,0.00000000) E(0.50000000,0.86602540) }
        scc2{ F(0.00000000,0.00000000) H(1.00000000,0.00000000) I(0.50000000,0.86602540) }
        scc3{ F(0.00000000,0.00000000) G(1.00000000,0.00000000) J(0.50000000,0.86602540) }
         这个图很难使用特殊规则淘汰，看来最终只能通过解方程达成目标。

ABACADAEBCBHBJCICJDEDHDIEFEGFGFHFJGIGJHI:
        scc0{ A(0.00000000,0.00000000) B(1.00000000,0.00000000) C(0.50000000,0.86602540) J(1.50000000,0.86602540) }
        scc1{ A(0.00000000,0.00000000) D(1.00000000,0.00000000) E(0.50000000,0.86602540) }
        scc2{ E(0.00000000,0.00000000) F(1.00000000,0.00000000) G(0.50000000,0.86602540) J(1.50000000,0.86602540) }
        scc3{ D(0.00000000,0.00000000) H(1.00000000,0.00000000) I(0.50000000,0.86602540) }
        很难通过特殊规则淘汰

ABACADAEBHBIBJCECFCIDEDGDJEHFGFHFIGHGJIJ:
        scc0{ A(0.00000000,0.00000000) C(1.00000000,0.00000000) D(-0.50000000,0.86602540) E(0.50000000,0.86602540) }
        scc1{ F(0.00000000,0.00000000) G(1.00000000,0.00000000) H(0.50000000,0.86602540) }
        scc2{ C(0.00000000,0.00000000) F(1.00000000,0.00000000) I(0.50000000,0.86602540) }
        scc3{ D(0.00000000,0.00000000) G(1.00000000,0.00000000) J(0.50000000,0.86602540) }
        scc4{ B(0.00000000,0.00000000) I(1.00000000,0.00000000) J(0.50000000,0.86602540) }
ABACADAEBDBIBJCECHCJDFDHEGEIFGFHFJGIGJHI:
        scc0{ A(0.00000000,0.00000000) B(1.00000000,0.00000000) D(0.50000000,0.86602540) }
        scc1{ A(0.00000000,0.00000000) C(1.00000000,0.00000000) E(0.50000000,0.86602540) }
        scc2{ D(0.00000000,0.00000000) F(1.00000000,0.00000000) H(0.50000000,0.86602540) }
        scc3{ E(0.00000000,0.00000000) G(1.00000000,0.00000000) I(0.50000000,0.86602540) }
        scc4{ F(0.00000000,0.00000000) G(1.00000000,0.00000000) J(0.50000000,0.86602540) }
AHAIAJBGBIBJCDCECGCIDFDGDJEFEHEIFHFJGHIJ:
        scc0{ C(0.00000000,0.00000000) D(1.00000000,0.00000000) G(0.50000000,0.86602540) }
        scc1{ E(0.00000000,0.00000000) F(1.00000000,0.00000000) H(0.50000000,0.86602540) }
        scc2{ C(0.00000000,0.00000000) E(1.00000000,0.00000000) I(0.50000000,0.86602540) }
        scc3{ D(0.00000000,0.00000000) F(1.00000000,0.00000000) J(0.50000000,0.86602540) }
        scc4{ A(0.00000000,0.00000000) B(1.50000000,0.86602540) I(1.00000000,0.00000000) J(0.50000000,0.86602540) }
AIAJBCBDBEBHCFCGCHDEDFDIEGEJFGFIGJHIHJIJ:
        scc0{ B(0.00000000,0.00000000) D(1.00000000,0.00000000) E(0.50000000,0.86602540) }
        scc1{ C(0.00000000,0.00000000) F(1.00000000,0.00000000) G(0.50000000,0.86602540) }
        scc2{ B(0.00000000,0.00000000) C(1.00000000,0.00000000) H(0.50000000,0.86602540) }
        scc3{ D(0.00000000,0.00000000) F(1.00000000,0.00000000) I(0.50000000,0.86602540) }
        scc4{ E(0.00000000,0.00000000) G(1.00000000,0.00000000) J(0.50000000,0.86602540) }
        scc5{ A(0.00000000,0.00000000) H(1.50000000,0.86602540) I(1.00000000,0.00000000) J(0.50000000,0.86602540) }
ABAFAJBCBGBJCHCICJDEDFDHDJEGEIEJFGFHGIHI:
        scc0{ D(0.00000000,0.00000000) F(1.00000000,0.00000000) H(0.50000000,0.86602540) }
        scc1{ E(0.00000000,0.00000000) G(1.00000000,0.00000000) I(0.50000000,0.86602540) }
        scc2{ C(0.00000000,0.00000000) H(1.00000000,0.00000000) I(0.50000000,0.86602540) }
        scc3{ A(0.00000000,0.00000000) B(1.00000000,0.00000000) C(1.50000000,0.86602540) J(0.50000000,0.86602540) }
        scc4{ D(0.00000000,0.00000000) E(1.00000000,0.00000000) J(0.50000000,0.86602540) }
ABACAJBFBHBJCGCICJDEDFDGDJEHEIEJFGFHGIHI:
        scc0{ D(0.00000000,0.00000000) F(1.00000000,0.00000000) G(0.50000000,0.86602540) }
        scc1{ B(0.00000000,0.00000000) F(1.00000000,0.00000000) H(0.50000000,0.86602540) }
        scc2{ C(0.00000000,0.00000000) G(1.00000000,0.00000000) I(0.50000000,0.86602540) }
        scc3{ E(0.00000000,0.00000000) H(1.00000000,0.00000000) I(0.50000000,0.86602540) }
        scc4{ A(0.00000000,0.00000000) B(1.00000000,0.00000000) C(-0.50000000,0.86602540) J(0.50000000,0.86602540) }
        scc5{ D(0.00000000,0.00000000) E(1.00000000,0.00000000) J(0.50000000,0.86602540) }

n=11
AGAHAKBIBJBKCFCHCJCKDEDFDGDKEFEHEIFJGIGJHIHKIJ:
        scc0{ D(0.00000000,0.00000000) E(1.00000000,0.00000000) F(0.50000000,0.86602540) }
        scc1{ E(0.00000000,0.00000000) H(1.00000000,0.00000000) I(0.50000000,0.86602540) }
        scc2{ C(0.00000000,0.00000000) F(1.00000000,0.00000000) J(0.50000000,0.86602540) }
        scc3{ B(0.00000000,0.00000000) G(1.50000000,0.86602540) I(1.00000000,0.00000000) J(0.50000000,0.86602540) }
        scc4{ A(0.00000000,0.00000000) C(1.50000000,0.86602540) H(1.00000000,0.00000000) K(0.50000000,0.86602540) }
AGAHAKBIBJBKCDCECICKDFDJDKEFEHEIFHFJGHGIGJHKIJ:
        scc0{ E(0.00000000,0.00000000) F(1.00000000,0.00000000) H(0.50000000,0.86602540) }
        scc1{ A(0.00000000,0.00000000) G(1.00000000,0.00000000) H(0.50000000,0.86602540) K(-0.50000000,0.86602540) }
        scc2{ C(0.00000000,0.00000000) E(1.00000000,0.00000000) I(0.50000000,0.86602540) }
        scc3{ D(0.00000000,0.00000000) F(1.00000000,0.00000000) J(0.50000000,0.86602540) }
        scc4{ B(0.00000000,0.00000000) G(1.50000000,0.86602540) I(1.00000000,0.00000000) J(0.50000000,0.86602540) }
        scc5{ C(0.00000000,0.00000000) D(1.00000000,0.00000000) K(0.50000000,0.86602540) }
AGAHAJBFBIBKCDCECHCIDEDJDKEFEGFHFJGIGKHIHJIKJK:
        scc0{ C(0.00000000,0.00000000) D(1.00000000,0.00000000) E(0.50000000,0.86602540) }
        scc1{ C(0.00000000,0.00000000) H(1.00000000,0.00000000) I(0.50000000,0.86602540) }
        scc2{ A(0.00000000,0.00000000) F(1.50000000,0.86602540) H(1.00000000,0.00000000) J(0.50000000,0.86602540) }
        scc3{ B(0.00000000,0.00000000) G(1.50000000,0.86602540) I(1.00000000,0.00000000) K(0.50000000,0.86602540) }
        scc4{ D(0.00000000,0.00000000) J(1.00000000,0.00000000) K(0.50000000,0.86602540) }
ABAHAJBIBKCDCECFCHDEDGDIEJEKFHFIFKGHGIGJHJIKJK:
        scc0{ C(0.00000000,0.00000000) D(1.00000000,0.00000000) E(0.50000000,0.86602540) }
        scc1{ C(0.00000000,0.00000000) F(1.00000000,0.00000000) H(0.50000000,0.86602540) }
        scc2{ D(0.00000000,0.00000000) G(1.00000000,0.00000000) I(0.50000000,0.86602540) }
        scc3{ A(0.00000000,0.00000000) G(1.50000000,0.86602540) H(1.00000000,0.00000000) J(0.50000000,0.86602540) }
        scc4{ B(0.00000000,0.00000000) F(1.50000000,0.86602540) I(1.00000000,0.00000000) K(0.50000000,0.86602540) }
        scc5{ E(0.00000000,0.00000000) J(1.00000000,0.00000000) K(0.50000000,0.86602540) }
ABAHAJBIBKCDCECFCGDGDHDJEFEHEIFJFKGIGKHIHJIKJK:
        scc0{ C(0.00000000,0.00000000) E(1.00000000,0.00000000) F(0.50000000,0.86602540) }
        scc1{ C(0.00000000,0.00000000) D(1.00000000,0.00000000) G(0.50000000,0.86602540) }
        scc2{ E(0.00000000,0.00000000) H(1.00000000,0.00000000) I(0.50000000,0.86602540) }
        scc3{ A(0.00000000,0.00000000) D(1.50000000,0.86602540) H(1.00000000,0.00000000) J(0.50000000,0.86602540) }
        scc4{ B(0.00000000,0.00000000) G(1.50000000,0.86602540) I(1.00000000,0.00000000) K(0.50000000,0.86602540) }
        scc5{ F(0.00000000,0.00000000) J(1.00000000,0.00000000) K(0.50000000,0.86602540) }
ABAHAIBJBKCDCECHCJDFDHDKEFEIEJFIFKGHGIGJGKHIJK:
        scc0{ C(0.00000000,0.00000000) D(1.00000000,0.00000000) H(0.50000000,0.86602540) }
        scc1{ E(0.00000000,0.00000000) F(1.00000000,0.00000000) I(0.50000000,0.86602540) }
        scc2{ A(0.00000000,0.00000000) G(1.50000000,0.86602540) H(1.00000000,0.00000000) I(0.50000000,0.86602540) }
        scc3{ C(0.00000000,0.00000000) E(1.00000000,0.00000000) J(0.50000000,0.86602540) }
        scc4{ D(0.00000000,0.00000000) F(1.00000000,0.00000000) K(0.50000000,0.86602540) }
        scc5{ B(0.00000000,0.00000000) G(1.50000000,0.86602540) J(1.00000000,0.00000000) K(0.50000000,0.86602540) }
ABACADAEBFBHBKCGCHCJDEDFDJEGEKFIFJGIGKHJHKIJIK:
        scc0{ A(0.00000000,0.00000000) D(1.00000000,0.00000000) E(0.50000000,0.86602540) }
        scc1{ D(0.00000000,0.00000000) F(1.00000000,0.00000000) I(1.50000000,0.86602540) J(0.50000000,0.86602540) }
        scc2{ C(0.00000000,0.00000000) H(1.00000000,0.00000000) J(0.50000000,0.86602540) }
        scc3{ E(0.00000000,0.00000000) G(1.00000000,0.00000000) I(1.50000000,0.86602540) K(0.50000000,0.86602540) }
        scc4{ B(0.00000000,0.00000000) H(1.00000000,0.00000000) K(0.50000000,0.86602540) }
ABACADAEBCBHBKCICJDEDFDJEGEKFGFHFJGIGKHJHKIJIK:
        scc0{ A(0.00000000,0.00000000) B(1.00000000,0.00000000) C(0.50000000,0.86602540) }
        scc1{ A(0.00000000,0.00000000) D(1.00000000,0.00000000) E(0.50000000,0.86602540) }
        scc2{ D(0.00000000,0.00000000) F(1.00000000,0.00000000) H(1.50000000,0.86602540) J(0.50000000,0.86602540) }
        scc3{ C(0.00000000,0.00000000) I(1.00000000,0.00000000) J(0.50000000,0.86602540) }
        scc4{ E(0.00000000,0.00000000) G(1.00000000,0.00000000) I(1.50000000,0.86602540) K(0.50000000,0.86602540) }
        scc5{ B(0.00000000,0.00000000) H(1.00000000,0.00000000) K(0.50000000,0.86602540) }
ABACADAEBFBHBJCGCHCKDFDIDKEGEIEJFGFJGKHJHKIJIK:
        scc0{ B(0.00000000,0.00000000) F(1.00000000,0.00000000) H(-0.50000000,0.86602540) J(0.50000000,0.86602540) }
        scc1{ E(0.00000000,0.00000000) I(1.00000000,0.00000000) J(0.50000000,0.86602540) }
        scc2{ C(0.00000000,0.00000000) G(1.00000000,0.00000000) H(-0.50000000,0.86602540) K(0.50000000,0.86602540) }
        scc3{ D(0.00000000,0.00000000) I(1.00000000,0.00000000) K(0.50000000,0.86602540) }
ABAEAGAIBFBHBICECGCHCJDFDGDHDKEFEJFKGKHJIJIKJK:
        scc0{ A(0.00000000,0.00000000) B(1.00000000,0.00000000) I(0.50000000,0.86602540) }
        scc1{ C(0.00000000,0.00000000) E(1.00000000,0.00000000) H(-0.50000000,0.86602540) J(0.50000000,0.86602540) }
        scc2{ D(0.00000000,0.00000000) F(1.00000000,0.00000000) G(-0.50000000,0.86602540) K(0.50000000,0.86602540) }
        scc3{ I(0.00000000,0.00000000) J(1.00000000,0.00000000) K(0.50000000,0.86602540) }
ABAEAGAIBFBHBICDCECHCJDFDGDKEFEJFKGHGKHJIJIKJK:
        scc0{ A(0.00000000,0.00000000) B(1.00000000,0.00000000) I(0.50000000,0.86602540) }
        scc1{ C(0.00000000,0.00000000) E(1.00000000,0.00000000) H(-0.50000000,0.86602540) J(0.50000000,0.86602540) }
        scc2{ D(0.00000000,0.00000000) F(1.00000000,0.00000000) G(-0.50000000,0.86602540) K(0.50000000,0.86602540) }
        scc3{ I(0.00000000,0.00000000) J(1.00000000,0.00000000) K(0.50000000,0.86602540) }
ABAEAFAIBGBHBICDCECHCJDFDGDKEFEJFKGHGKHJIJIKJK:
        scc0{ A(0.00000000,0.00000000) E(1.00000000,0.00000000) F(0.50000000,0.86602540) }
        scc1{ B(0.00000000,0.00000000) G(1.00000000,0.00000000) H(0.50000000,0.86602540) }
        scc2{ A(0.00000000,0.00000000) B(1.00000000,0.00000000) I(0.50000000,0.86602540) }
        scc3{ C(0.00000000,0.00000000) E(1.00000000,0.00000000) H(-0.50000000,0.86602540) J(0.50000000,0.86602540) }
        scc4{ D(0.00000000,0.00000000) F(1.00000000,0.00000000) G(-0.50000000,0.86602540) K(0.50000000,0.86602540) }
        scc5{ I(0.00000000,0.00000000) J(1.00000000,0.00000000) K(0.50000000,0.86602540) }
AEAHAIAJBFBGBIBKCFCGCHCJDEDGDHDKEFEJFKGJHKIJIK:
        scc0{ A(0.00000000,0.00000000) E(1.00000000,0.00000000) I(-0.50000000,0.86602540) J(0.50000000,0.86602540) }
        scc1{ C(0.00000000,0.00000000) G(1.00000000,0.00000000) J(0.50000000,0.86602540) }
        scc2{ B(0.00000000,0.00000000) F(1.00000000,0.00000000) I(-0.50000000,0.86602540) K(0.50000000,0.86602540) }
        scc3{ D(0.00000000,0.00000000) H(1.00000000,0.00000000) K(0.50000000,0.86602540) }
ABAIAJBEBHBKCECGCJCKDGDHDIDKEFEKFHFIFJGHGJIJIK:
        scc0{ D(0.00000000,0.00000000) G(1.00000000,0.00000000) H(0.50000000,0.86602540) }
        scc1{ C(0.00000000,0.00000000) G(1.00000000,0.00000000) J(0.50000000,0.86602540) }
        scc2{ A(0.00000000,0.00000000) F(1.50000000,0.86602540) I(1.00000000,0.00000000) J(0.50000000,0.86602540) }
        scc3{ B(0.00000000,0.00000000) C(1.50000000,0.86602540) E(1.00000000,0.00000000) K(0.50000000,0.86602540) }
        scc4{ D(0.00000000,0.00000000) I(1.00000000,0.00000000) K(0.50000000,0.86602540) }
ABAIAJBCBGBKCECHCKDFDHDIDKEIEJEKFGFJFKGHGJHIIJ:
        scc0{ D(0.00000000,0.00000000) H(1.00000000,0.00000000) I(0.50000000,0.86602540) }
        scc1{ F(0.00000000,0.00000000) G(1.00000000,0.00000000) J(0.50000000,0.86602540) }
        scc2{ A(0.00000000,0.00000000) E(1.50000000,0.86602540) I(1.00000000,0.00000000) J(0.50000000,0.86602540) }
        scc3{ B(0.00000000,0.00000000) C(1.00000000,0.00000000) E(1.50000000,0.86602540) K(0.50000000,0.86602540) }
        scc4{ D(0.00000000,0.00000000) F(1.00000000,0.00000000) K(0.50000000,0.86602540) }
ABAIAJBCBEBKCGCJCKDGDHDIDKEFEHEKFHFIFJGHGJIJIK:
        scc0{ E(0.00000000,0.00000000) F(1.00000000,0.00000000) H(0.50000000,0.86602540) }
        scc1{ D(0.00000000,0.00000000) G(1.00000000,0.00000000) H(0.50000000,0.86602540) }
        scc2{ C(0.00000000,0.00000000) G(1.00000000,0.00000000) J(0.50000000,0.86602540) }
        scc3{ A(0.00000000,0.00000000) F(1.50000000,0.86602540) I(1.00000000,0.00000000) J(0.50000000,0.86602540) }
        scc4{ B(0.00000000,0.00000000) C(1.00000000,0.00000000) E(-0.50000000,0.86602540) K(0.50000000,0.86602540) }
        scc5{ D(0.00000000,0.00000000) I(1.00000000,0.00000000) K(0.50000000,0.86602540) }
ABAIAJBCBDBKCGCICKDHDJDKEFEIEJEKFGFHFKGHGIHJIJ:
        scc0{ F(0.00000000,0.00000000) G(1.00000000,0.00000000) H(0.50000000,0.86602540) }
        scc1{ C(0.00000000,0.00000000) G(1.00000000,0.00000000) I(0.50000000,0.86602540) }
        scc2{ D(0.00000000,0.00000000) H(1.00000000,0.00000000) J(0.50000000,0.86602540) }
        scc3{ A(0.00000000,0.00000000) E(1.50000000,0.86602540) I(1.00000000,0.00000000) J(0.50000000,0.86602540) }
        scc4{ B(0.00000000,0.00000000) C(1.00000000,0.00000000) D(-0.50000000,0.86602540) K(0.50000000,0.86602540) }
        scc5{ E(0.00000000,0.00000000) F(1.00000000,0.00000000) K(0.50000000,0.86602540) }
AIAJAKBCBDBFBJCECGCKDGDHDIEFEHEIFIFJGIGKHJHKJK:
        scc0{ E(0.00000000,0.00000000) F(1.00000000,0.00000000) I(0.50000000,0.86602540) }
        scc1{ D(0.00000000,0.00000000) G(1.00000000,0.00000000) I(0.50000000,0.86602540) }
        scc2{ B(0.00000000,0.00000000) F(1.00000000,0.00000000) J(0.50000000,0.86602540) }
        scc3{ C(0.00000000,0.00000000) G(1.00000000,0.00000000) K(0.50000000,0.86602540) }
        scc4{ A(0.00000000,0.00000000) H(1.50000000,0.86602540) J(1.00000000,0.00000000) K(0.50000000,0.86602540) }
AIAJAKBCBDBHBICDCFCJDGDKEFEGEHEIFIFJGIGKHJHKJK:
        scc0{ B(0.00000000,0.00000000) C(1.00000000,0.00000000) D(0.50000000,0.86602540) }
        scc1{ E(0.00000000,0.00000000) F(1.00000000,0.00000000) G(-0.50000000,0.86602540) I(0.50000000,0.86602540) }
        scc2{ C(0.00000000,0.00000000) F(1.00000000,0.00000000) J(0.50000000,0.86602540) }
        scc3{ D(0.00000000,0.00000000) G(1.00000000,0.00000000) K(0.50000000,0.86602540) }
        scc4{ A(0.00000000,0.00000000) H(1.50000000,0.86602540) J(1.00000000,0.00000000) K(0.50000000,0.86602540) }
AIAJAKBCBDBFBICECFCIDEDGDJEHEKFJFKGHGIGJHIHKJK:
        scc0{ B(0.00000000,0.00000000) C(1.00000000,0.00000000) F(0.50000000,0.86602540) I(0.50000000,-0.86602540) }
        scc1{ G(0.00000000,0.00000000) H(1.00000000,0.00000000) I(0.50000000,0.86602540) }
        scc2{ D(0.00000000,0.00000000) G(1.00000000,0.00000000) J(0.50000000,0.86602540) }
        scc3{ E(0.00000000,0.00000000) H(1.00000000,0.00000000) K(0.50000000,0.86602540) }
        scc4{ A(0.00000000,0.00000000) F(1.50000000,0.86602540) J(1.00000000,0.00000000) K(0.50000000,0.86602540) }

mathe

使用上一个版本的过滤程序效果太差，结果在n稍微大一些时增加很快，然后对代码做了一些更新。
如果发现一个SCC外部一个点和这个SCC有三条已知长度的边相连，那么通常就可以算出这个点相对这个SCC的坐标，可以将它加入这个SCC.
如果两个SCC有一个公共点并且至少还有两条两个SCC之间的已知长度的边，那么通常也可以计算出两个SCC的相对关系，可以将它们合并。
使用这两条规则后，数据增长稍微慢了一些，如下面附件，可以计算到n=16的情况，只是对于较大的n,出来的候选解还是比较多。
比如对于n=14,根据前面已知数据，最大边长应该只有33条边，但是我这里搜索出来的还有多大35条边的候选解，需要一一继续淘汰。
所以关键后面还需要对过滤程序进行进一步加强。
另外现在代码写得还比较仓促，很可能还有bug存在，后续需要使用更多数据去调试验证，增加可靠性。

data6.tgz (564.88 KB, 下载次数: 3)

2025-4-23 22:21 上传

点击文件名下载附件

mathe

光上面处理还是有些不够，最终还是得解多项式方程组，这一步可以将singular用上。
对于n=7, 留下最长边为12，对应的singular方程文件为

1. //num of scc 1, num of point 0
   
2. //x[A]=0+0*w
   
3. //y[A]=0+0*w
   
4. //x[B]=1+0*w
   
5. //y[B]=0+0*w
   
6. //x[C]=-1/2+0*w
   
7. //y[C]=0+1/2*w
   
8. //x[D]=1+0*w
   
9. //y[D]=0+1*w
   
10. //x[E]=3/2+0*w
    
11. //y[E]=0+1/2*w
    
12. //x[F]=0+0*w
    
13. //y[F]=0+1*w
    
14. //x[G]=1/2+0*w
    
15. //y[G]=0+1/2*w
    
16. ring r=(0,w),(v(1..0)),dp;
    
17. minpoly=w^2-3;
    

复制代码

这里所有的点的坐标都已经已知了，所以不需要求解，其中w是\(\sqrt{3}\)。
n=8,留下最多14条边，对应还有9个singular文件，其中有8个带输出结果（没有输出结果的文件应该是不需要求解，所有坐标已知）
比如其中文件AFAGBCBFBHCGCHDEDGDHEFEHFHGH.sg.0

1. //num of scc 1, num of point 1
   
2. //x[A]=v(1)
   
3. //y[A]=v(2)
   
4. //x[B]=0+0*w
   
5. //y[B]=0+0*w
   
6. //x[C]=1+0*w
   
7. //y[C]=0+0*w
   
8. //x[D]=1+0*w
   
9. //y[D]=0+1*w
   
10. //x[E]=0+0*w
    
11. //y[E]=0+1*w
    
12. //x[F]=-1/2+0*w
    
13. //y[F]=0+1/2*w
    
14. //x[G]=3/2+0*w
    
15. //y[G]=0+1/2*w
    
16. //x[H]=1/2+0*w
    
17. //y[H]=0+1/2*w
    
18. ring r=(0,w),(v(1..2)),dp;
    
19. minpoly=w^2-3;
    
20. //edge FA
    
21. poly f0=((-1/2+0*w)-(v(1)))^2+((0+1/2*w)-(v(2)))^2-1;
    
22. //edge GA
    
23. poly f1=((3/2+0*w)-(v(1)))^2+((0+1/2*w)-(v(2)))^2-1;
    
24. //Diamond AHFG
    
25. poly f2=(v(1))+(1/2+0*w)-(-1/2+0*w)-(3/2+0*w);
    
26. poly f3=(v(2))+(0+1/2*w)-(0+1/2*w)-(0+1/2*w);
    
27. //Diamond FGAH
    
28. poly f4=(-1/2+0*w)+(3/2+0*w)-(v(1))-(1/2+0*w);
    
29. poly f5=(0+1/2*w)+(0+1/2*w)-(v(2))-(0+1/2*w);
    
30. ideal i=f0,f1,f2,f3,f4,f5;
    
31. ideal ii=std(i);
    
32. ii;
    
33. dim(ii);
    

复制代码

可以看出，还有两个变量v(1),v(2)需要计算，对应singular处理后输出文件AFAGBCBFBHCGCHDEDGDHEFEHFHGH.sg.0.out

1.                      SINGULAR                                 /  Development
   
2. A Computer Algebra System for Polynomial Computations       /   version 4.1.1
   
3.                                                            0<
   
4. by: W. Decker, G.-M. Greuel, G. Pfister, H. Schoenemann     \   Feb 2018
   
5. FB Mathematik der Universitaet, D-67653 Kaiserslautern        \  Debian 1:4.1.1-p2+ds-4+b2
   
6. ii[1]=2*v(2)+(-w)
   
7. ii[2]=2*v(1)-1
   
8. 0
   
9. Auf Wiedersehen.
   

复制代码

可以看出唯一解v(1)=1/2,v(2)=w/2。检验时可以发现H和A两个点坐标相同，所以是非法解，需要淘汰。但是文件AFAGBCBDBHCECHDFDHEGEHFGFHGH.sg.0没有输出文件，所有坐标已知，是合法解。
附件是n=11以内所有候选解，需要再处理一下。
等距.zip (50.24 KB, 下载次数: 3)

2025-4-25 08:08 上传

点击文件名下载附件