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

medie2005

呵呵，估计就是穷举来证明的。

eyond

原帖由 mathe 于 2008-10-31 10:12 发表 网络上搜索到那篇文章了,很可惜,他的结论是在n充分大的时候才成立的.而我们考虑的是n很小时候的情况.

mathe是说我说的那个文章吗？我刚才试着传上去整篇原文的照片，可是提示说“来路不正”什么的，说这边的机子屏蔽掉了。我不懂。 还需要上传吗？ 另外，昨夜想到一个方法能证明问题二最高解30是否存在。道理很简单，算起来有点难度。估计明天能有结果。

liangbch

你为什么要传照片呢？如果原文是pdf,chm等系统支持的格式，直接上传好了，如果不是系统规定的格式，那么请压缩为zip文件或者rar文件再上传。 by the way, 如果必须要上传jpg,请适当将调整其压缩比，使得文件更小些，这样在显示网页时也会快很多。

liangbch

那篇文章找到了，见 http://www.emis.ams.org/journals/EJC/Volume_4/PDF/v4i1r1.pdf， 原文为pdf格式，大小为 98k，17页。 直接上传只需要98K，而你仅仅上传了1页，就占了180多K,要懂得节省网络成本。

eyond

是PDF格式的，我不懂，上网下东西打开之后，也不会复制到WORD里面，只好剪屏了，一共剪了28张呢，怕占地方所以先传一张上去，现在大家都找到了所以就不传了哈。

无心人

呵呵 以后就知道了么

eyond

原帖由 无心人 于 2008-10-14 12:53 发表 您是否还要考虑在北京和在上海是否可能存在不同的树的排列的解 因为地形不同啊 大哥是否知道什么叫图论啊 数学抽象明白不？ 20棵树植树问题等价于n个不重合的直线相交于20个点，每个直线恰好有4个交点 ...

无心人的这个结论是怎么得出来的？ 结论：20棵树植树问题等价于n个不重合的直线相交于20个点，每个直线恰好有4个交点 …… 确认这个结论正确吗？ 我怎么感觉这个结论不对劲？？？？ 请各位老师指教，无心人说说看是怎么回事；mathe也指教指教一下。 如果这个结论结果出来，那么，我敢肯定种树问题又要上个台阶了。。。。

mathe

无心人这个只不过是直接将这个问题用数学概念进行描述而已. 倒是利用对偶原理可以知道这个问题等价于找到20条不同的直线和n个不同的交点,其中每个交点正好有4条直线通过.

eyond

mathe ？运用对偶原理应该是把这个结论等同与问题二，即字母排列对吧？ 按照无心人的意思应该是----找到n条直线，这n条直线相交得出20个点，（就是20棵树）。要求是：每条线必须与其他线相交四次。（就是每行4棵）。 无心人这样的结论如果成立，那么30的解是否存在就好说了： 设论：30条直线相交得出20个点，要求每6条线交于1点；且每条线只能用4次。 这个设论成立就表示有30解，不成立则表明没有。 同样我们可以知道，以前我们就掌握了问题二的24，25，26，27，28，的解。那么按照点线兑换不就知道24，25，26，27，28条线怎么组成交点了吗？ 这样就大概是解决了问题一了吧。 我认为，现在最需要的是证明无心人的这个结论的正确性。

无心人

你要清楚 我说这个并没有 对题目有任何的简化 只是一种变形吧 所以并不要太奢求 你如果真明白这个题目 你也能得到这结论