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

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下运行，我还需要修改一下代码