数学研发论坛

 找回密码
 欢迎注册
查看: 345|回复: 3

[讨论] 加权植树问题

[复制链接]
发表于 2021-5-27 01:56:47 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
n 棵树3棵一行的有t3行,4棵一行的有t4行,没有更多棵的行。
求行数的加权和\[S(n)=t_3+2t_4\]的最大值。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2021-5-27 02:20:09 | 显示全部楼层
为什么是`t_3+2t_4`, 而不是`3t_3+4t_4`?

起初是想用`3t_3+4t_4`, 因为有`3t_3+4t_4=\sum d\cdot V_d`, (`V_d`---度为d的点数),似有一定的图论意义。
但是,一来担心系数3与4差别较小,可能导致最大解全是3树行,没有4树以上行。
二则,同一行的树,应该认为两两有边相连,而不是仅相邻的树关联。
如此,一个 3树行就有3条边, 一个4树行就有6条边,使上述关系式仍然成立。约去公因子3,系数便取成了1和2。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-5-27 06:27:05 | 显示全部楼层
https://bbs.emath.ac.cn//forum.p ... 0028&fromuid=20
t2≥3+t4
C(n,2)≥t2+3t3+6t4≥3+3t3+7t4, 看来还是应该尽量取3树行
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2021-5-27 08:57:06 | 显示全部楼层
起初并没有想要限制在最多4树行,想的是求 `3t_3+4t_4+\cdots+k\cdot t_k+\cdots+n\cdot t_n`。
但是感觉线性权重系数梯度较缓,不利于多树行,可能结果都是3树行。
改为考察  `3t_3+6t_4+\cdots+C_k^2\cdot t_k+\cdots+C_n^2\cdot t_n`,
又发现权重系数梯度太大,导致 n 树全在一行,结果就是`C_n^2`。
我无法提出一个介于 k 与 C(k,2)之间具有明显图论意义的权重系数,只好限制同行的树数。
2树总有一行,所以3树是基本约束,4树可关联到射影几何的不变量---交比,5树以上我不知道有什么意义
所以,就限制到最多4树行了。
由于C(k,2)是加速增长的,在k较小时加速度小,系数差别可能还是嫌小,不利于4树行。
如果真如 mathe 楼上所说,4树行不给力,那也许放宽到`3t_3+6t_4+10t_5`就能抑制3树行了。
或者,能否提出一个介中的权重系数`a_k`,使得`\sum a_k\cdot t_k`的驻点不走极端?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2021-7-29 16:35 , Processed in 0.063154 second(s), 21 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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