数学研发论坛

 找回密码
 欢迎注册
楼主: 0→∞

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

  [复制链接]
发表于 2009-7-6 12:32:01 | 显示全部楼层
上次输入数字错误,其中“大于5”,应为“大于4”:
如要证明t4=26是不存在的。只要证明
平面上任意20根直线,若恰3根直线相交点的共有t3个(无恰超过4根直线相交点),且这20根直线将平面划分成的四边形个数+2倍五边形个数+3倍六边形个数+4倍七边形个数+5倍八边形个数+3t3大于4。则恰4根直线相交点的个数小于26个。(当然也不容易证明)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-7-6 12:36:46 | 显示全部楼层
也就是说,若存在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。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-7-6 15:32:29 | 显示全部楼层
呵呵,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条线,
      肯定不可能)"
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-7-7 10:33:36 | 显示全部楼层
呵呵,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条线,肯定不可能”有问题,因为可能有很多三边形。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-7-7 11:04:02 | 显示全部楼层
不好意思,我理解有误
"5-(3t3+f4+2f5+3f6+…)=0"并不包含三角形区域的计数,那三线共点几乎就没多大利用价值了....
那么如何计算这些区域中有多少三角形呢(最小单元,即不包含其它多边形的区域)?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-7-8 10:40:43 | 显示全部楼层
这些区域中有多少三角形是不确定的,由这20根直线具体位置确定,有可能很多,也有可能很少。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-11-5 11:41:18 | 显示全部楼层
现在想到一个不错的解的过滤(以及求解)方法,比原先的解方程方法快很多。
现在如果在我的双核的机器上运行我最感兴趣的部分数据(从17点13边开始构造出20点24边的结果),完全处理需要大概240天左右。也就是如果有8台类似的机器可以1个月处理完毕。
而余下的部分数据过去同无心人处理过(不过现在发现可能有bug,需要重新处理一下),那部分工作量应该更加小一些。
求解算法如图:
第一步选择4个任意三点不共线的点假设它们的坐标,如图1,那么它们的连线的方程也可以得出
图中无论点还是直线都是用齐次坐标表示[点(a,b,c)表示点(a/c,b/c)。直线(a,b,c)表示ax+by+c=0]
g1.GIF
如图2,反复根据直线交点和交点确定的直线可以得出更多的结果
g2.GIF
如图3,取一个在某个已知坐标直线上的未知点G,假设其坐标(包含一个参数t)
然后反复选择直线交点或点确定的直线(要求至少一条直线或一个点坐标不含参数t)得出更多点和线坐标(t的线性方程),最后可以得出t或矛盾或者无法确定是否有解
g3.GIF
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-11-5 14:20:05 | 显示全部楼层
是的,对于已知的一组点线关系,(就是类似:ABCD-AEGF-……的东东)。对于所有潜在的构型,它们非常可能都是所谓的5点生成,(即:包括在5点(例如(1,0,0),(0,1,0),(0,0,1),(0,1,1),(0,1,t))经过点生线、线生点……所形成的图形中),而且一般都是来回三次就够了。构型是否存在,取决于t的方程有没有除了0或1以外的实根。
因为计算一个构型如何5点生成是不用解方程的,所以比较快。
这种思路我想过,而我却无法编程列举出所有的潜在构型。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-11-6 13:21:47 | 显示全部楼层
现在想到一个不错的解的过滤(以及求解)方法,比原先的解方程方法快很多。
现在如果在我的双核的机器上运行我最感兴趣的部分数据(从17点13边开始构造出20点24边的结果),完全处理需要大概240天左右。也就是如果有 ...
mathe 发表于 2009-11-5 11:41


是否可将最后的计算程序分成20个左右执行程序后公布在此,感兴趣者可一起计算,算完将计算结果返回给您(这样可以早一点得出结果),不知是否可行?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-11-6 13:50:16 | 显示全部楼层
现在的程序输入数据太大。我是将所有17棵树13行的数据作为输入,有6G多。
不过应该可以改成用16棵树11行的数据作为输入,不过即使这样,输入数据还有40多M.还是有点麻烦,不过基本上可能还是可行的。
另外现在我的程序在cygwin下运行,我还需要修改一下代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2021-6-17 12:53 , Processed in 0.054801 second(s), 17 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表