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

sheng_jianguo

上次输入数字错误，其中“大于5”，应为“大于4”： 如要证明t4=26是不存在的。只要证明 平面上任意20根直线，若恰3根直线相交点的共有t3个（无恰超过4根直线相交点），且这20根直线将平面划分成的四边形个数+2倍五边形个数+3倍六边形个数+4倍七边形个数+5倍八边形个数+3t3大于4。则恰4根直线相交点的个数小于26个。（当然也不容易证明）

sheng_jianguo

也就是说,若存在t4=26,则只有八种情况以下为被直线分割成的区域形状数目) (1) 四边形个数4个, 五边形1个,其它多边形无 (2) 三边形1个,五边形1个,其它多边形无(最多3*1+5*1=8 数学星空 发表于 2009-7-3 14:31

分析有问题。 若有t4=26（即20棵树，每行4棵的有26行）则必须满足5-(3t3+f4+2f5+3f6+…)=0 而不是3t3+f4+2f5+3f6+…=20。

数学星空

呵呵,sheng_jianguo没弄明白我的意思哟... 的确我将t3误作为f3了,再重新整理一下: 若有t4=26（即20棵树，每行4棵的有26行）则必须满足5-(3t3+f4+2f5+3f6+…)=0 ........(1) (1)的解只有如下八种 1. t3=0, f4=5, f5=f6=f7=.....=0 2. t3=0, f4=1, f5=2, f6=f7=...=0 3. t3=0 , f4=2, f6=1, f5=f7=...=0 4. t3=0, f4=1, f7=1, f5=f6=f8=...=0 5. t3=0, f5=f6=1, f7=f8=...=0 6. t3=0, f8=1, f5=f6=f7=f9=...=0 7. t3=1, f4=2, f5=f6=...=0 8. t3=1, f4=f6=f7=...=0 即(1) 三点共线的没有,四边形个数5个,其它多边形无 (2) 三点共线的没有,四边形1个,五边形2个,其它多边形无(最多4*1+5*2=14<20不可能) (3) 三点共线的没有,四边形2个,六边形1个,其它多边形无(最多4*2+6*1=14<20不可能) (4) 三点共线的没有,四边形1个,七边形1个,其它多边形无(最多4*1+7*1=11<20不可能) (5)三点共线的没有,五边形1个,六边形1个,其它多边形无(最多5*1+6*1=11<20不可能) (6)三点共线的没有,八边形1个,其它多边形无(最多8*1=8<20不可能) (7)三点共线的1个,四边形2个,其它多边形无(最多4*2+3=11<20不可能) (8)三点共线的1个,五边形1个,其它多边形无(最多5+3=8<20不可能) 即只有一种可能性,四边形5个的区域分布....剩下就是如何构造了 注:因为共有20条线,而 "三点共线的没有,四边形1个,五边形2个,其它多边形无(这种情形最多4*1+5*2=14条线小于20条线, 肯定不可能)"

sheng_jianguo

呵呵,sheng_jianguo没弄明白我的意思哟... 的确我将t3误作为f3了,再重新整理一下: 若有t4=26（即20棵树，每行4棵的有26行）则必须满足5-(3t3+f4+2f5+3f6+…)=0 ........(1) (1)的解只有如下八种 1. t ... 注:因为共有20条线,而 "三点共线的没有,四边形1个,五边形2个,其它多边形无(这种情形最多4*1+5*2=14条线小于20条线, 肯定不可能)" 数学星空 发表于 2009-7-6 15:32

数学星空的想法很有意思，但有几个问题： t3在对偶中是恰三线共点的个数，不是“三点共线”。 “这种情形最多4*1+5*2=14条线小于20条线,肯定不可能”有问题，因为可能有很多三边形。

数学星空

不好意思,我理解有误 "5-(3t3+f4+2f5+3f6+…)=0"并不包含三角形区域的计数,那三线共点几乎就没多大利用价值了.... 那么如何计算这些区域中有多少三角形呢(最小单元,即不包含其它多边形的区域)?

sheng_jianguo

这些区域中有多少三角形是不确定的，由这20根直线具体位置确定，有可能很多，也有可能很少。

mathe

现在想到一个不错的解的过滤（以及求解）方法，比原先的解方程方法快很多。 现在如果在我的双核的机器上运行我最感兴趣的部分数据（从17点13边开始构造出20点24边的结果），完全处理需要大概240天左右。也就是如果有8台类似的机器可以1个月处理完毕。 而余下的部分数据过去同无心人处理过（不过现在发现可能有bug，需要重新处理一下),那部分工作量应该更加小一些。 求解算法如图： 第一步选择4个任意三点不共线的点假设它们的坐标，如图1，那么它们的连线的方程也可以得出 图中无论点还是直线都是用齐次坐标表示[点(a,b,c)表示点(a/c,b/c)。直线(a,b,c)表示ax+by+c=0] 如图2，反复根据直线交点和交点确定的直线可以得出更多的结果 如图3，取一个在某个已知坐标直线上的未知点G,假设其坐标（包含一个参数t） 然后反复选择直线交点或点确定的直线（要求至少一条直线或一个点坐标不含参数t）得出更多点和线坐标（t的线性方程），最后可以得出t或矛盾或者无法确定是否有解

zgg___

是的，对于已知的一组点线关系，（就是类似：ABCD-AEGF-……的东东）。对于所有潜在的构型，它们非常可能都是所谓的5点生成，（即：包括在5点（例如(1,0,0),(0,1,0),(0,0,1),(0,1,1),(0,1,t)）经过点生线、线生点……所形成的图形中），而且一般都是来回三次就够了。构型是否存在，取决于t的方程有没有除了0或1以外的实根。 因为计算一个构型如何5点生成是不用解方程的，所以比较快。 这种思路我想过，而我却无法编程列举出所有的潜在构型。

sheng_jianguo

现在想到一个不错的解的过滤（以及求解）方法，比原先的解方程方法快很多。 现在如果在我的双核的机器上运行我最感兴趣的部分数据（从17点13边开始构造出20点24边的结果），完全处理需要大概240天左右。也就是如果有 ... mathe 发表于 2009-11-5 11:41

是否可将最后的计算程序分成20个左右执行程序后公布在此，感兴趣者可一起计算，算完将计算结果返回给您（这样可以早一点得出结果），不知是否可行？

mathe

现在的程序输入数据太大。我是将所有17棵树13行的数据作为输入，有6G多。 不过应该可以改成用16棵树11行的数据作为输入，不过即使这样，输入数据还有40多M.还是有点麻烦，不过基本上可能还是可行的。 另外现在我的程序在cygwin下运行，我还需要修改一下代码