果树问题讨论:这两个问题等价么？

mathe · 发表于 2009-12-19 11:45:02

现在我提供一个程序，这个程序可以将任何一个问题二（包括问题一）的结果（要求不超过20棵树）转化为一种标准化表示，也就是说，如果两个方案等价，虽然由于字母排序不同看起来不同，它们的输出会相同。
此外除了输出标准化结果以外，另外输出一行字母对应关系来表示点的变换过程。
比如对于过去比较早产生的程序的标准化输入和现在的字母顺序会相反
例子:
ABCPAHIQAJKRBHLRBJMQCLNQCMORDEIKDHMNDOPQEJLOENPRFGQRFHKOFILPGIJNGKMP
CFHLEIJLCGJMDHKMABLMACENDGINBCDOEFKOHJNOADFPBEGPBFIQAGKQAHIRBJKRCPQR
PMKGNJIGPLIFOKHFRQGFRPNEOLJEQPODNMHDKIEDROMCQNLCQMJBRLHBRKJAQIHAPCBA
其中第一行是输入，第二行是标准化输出，第三行是每个字母在原图像中的字母（可以看到这里正好是第一行的逆序）

norm.zip (11.63 KB, 下载次数: 9)

mathe · 发表于 2009-12-19 16:59:53

下面这个是求解程序。
在标准输入中输入一个可能解，如果程序求解成功或无法判断是否无解，会输出一组方程，输出的方程可以直接用maxima求解（当然有可能太复杂而maxima也无法求解，大家也可以使用其他更好的数学软件对输出的方程组进行处理）

solver.zip (34.02 KB, 下载次数: 12)

mathe · 发表于 2009-12-19 17:04:59

这里这个附件是一个Pari/gp程序，可以对一个数据进行射影变换。
只是Pari/gp输入输出我不会做，需要通过修改前面几个函数达到。
其中假设输入数据中有一个参数，参数满足方程get_mod_poly().
get_float_t()指定一个浮点参数（可以用于画图）。
get_node_info()给定每个点的坐标，采用射影坐标（正常点为(x,y,1),无穷远点可为(1,k,0)，k为这个方向的斜率）
其中函数verify_input()用于确认输入是正确的（确保用户输入过程没有错误）
而verify_inputs()函数除了验证所有的4点共线成立外，还要确保没有5点共线。如果这个函数也通过，说明前面用solver解出的解是正确的候选解。
show_algebra函数可以用来以图像方式显示

mathe · 发表于 2009-12-20 12:45:58

现在在2#中给出了14到18棵树的很多结果（包含所有最优结果，18棵还不全，19~20棵树以后再继续添加）。以后大家有空还可以将14棵到20棵的所有最优结果整理一下，将图画出来。而且最好能够通过射影变换，将图变换得更加漂亮。

hujunhua · 发表于 2010-1-17 01:05:55

这两个问题不等价。问题一（即果树问题）属于实射影几何，问题二属于有限射影几何。

实射影几何与有限射影几何一个本质区别是：前者遵守Desargues公理，后者不遵守。这个区别导致这样一个结果：在有限射影几何中的共直线的3点，在实射影几何中不一定找得到模型。

hujunhua · 发表于 2010-1-17 01:50:06

比如，最小的有限射影平面包含7个点和7条直线。每点恰好结着3条直线，每条直线恰好穿过3个点。

如果你要尽力在欧氏平面（可视为实射影平面的有限部分）上画出其模型，就会得到一个类似这样的构图：一个三角形以及它的3条中线，3个中点和重心。
7个点有了：3个顶点，3个中点，再算上重心
6条直线：3条边，3条中线。还差一条直线在哪里呢，你清理一下哪些点还不够3条直线就会发现，剩下的那条直线是经过3个中点的！

在实射影平面上，三角形的3个中点当然不可能共线。很直观吧，但是真要证明起来还有点麻烦呢，不信你试试看。

mathe · 发表于 2010-1-17 17:18:36

google了一下,有限射影平面是指有限域内的射影平面,所以同问题二也不等价.而选择不同的有限域,得到的有限射影平面也不等价.

wayne · 发表于 2013-12-11 23:38:51

hujunhua 发表于 2010-1-17 01:50
比如，最小的有限射影平面包含7个点和7条直线。每点恰好结着3条直线，每条直线恰好穿过3个点。

如果你要 ...

7条线,7个点,又叫Fano平面吧

wayne · 发表于 2013-12-26 16:04:07

mathe 发表于 2009-12-17 10:47
我分析出来是王兴君,eyond,和我给出的那三个结果是等价的。可以分析它们的点线关系会发现它们是一致的。而 ...

是的，关于23行的解，算出来在射影平面内的解有两个，一个是有理数的，一个是无理数的。
刚才核查了，发现王兴君,eyond 给的图形都源自于那个有理数解的某种射影变换。

我待会整理一下，提供详细的变换矩阵，坐标点信息。

wayne · 发表于 2013-12-27 16:43:35

欧氏平面内点线关系不同的图案已经整理完毕(半手工半程序)，均附带坐标信息，总共有16个图案完全不一样。
还有少量我直接扔弃了，因为这些图的点太集中，辨识度无法提高。

此时才发现虽然有两个跟 eyond一样，由一个大三角形囊括着，但内部细节却是不一样的，很可能是我在肉眼审判图的类型的时候，遗漏了eyond的图案。有时间再审查一下。
压缩包已经上传到QQ群6807814的空间

账号		自动登录	找回密码
密码			欢迎注册

[求助] 果树问题讨论:这两个问题等价么？