仓库管理员的最优入库方案问题

mathe

f(n,n+1)还同n+1个点的普通树的数目匹配，这个结论也挺奇怪的

hujunhua

我唯一能想到的构造方法就是把一个`\text{Tree}(E_1, n+1)`的结点全当作白点，然后在每条边上，或者说是每两个相邻白点之间添一个黑点，或可构成一个`G(E_2, n+1, n)`?
由此导出的`G(E_2, n+1, n)`（如果是的话）的每个黑点的度都是2。那么，是否对于任一`G(E_2, n+1, n)`，其每个黑点的度都是2？ 诚如是，才可以无视黑点, 将`G(E_2, n+1, n)`看作一个`\text{Tree}(E_1, n+1)`.  

对于n=2,3,4,5，这两个问题的回答是肯定的，所以这样的一一对应是成立的。
以下证明对所有的 n，以上两个问题的回答也肯定的，从而一一对应是成立的。

一）把一个`\text{Tree}(E_1, n+1)`的结点全当作白点，然后在每条边上，或者说是每两个相邻白点之间添一个黑点，构成的树是一个`G(E_2, n+1, n)`.
证明： 只需要证明这样得到的树，它的带权邻接矩阵是非负矩阵。也就是，可以给它的每边赋一非负权，使得任一黑点权汇为n+1,   任一白点权汇为n.
  由于任一黑点`B_i`皆2度点，它将`G(E_2, n+1, n)`分成两个桥接的子树: 左子树`L_i`, 右子树`R_i`, 记其上的白点数分别为`l_i, r_i`，则黑点数为`l_i-1,r_i-1`,  `l_i+r_i=n+1`
按赋权公式，`B_i`的左侧边的权重`=n\cdot l_i-(n+1)(l_i-1)=n+1-l_i=r_i>0`, 右侧边的权重`=n+1-r_i=l_i>0`.

二）G(E, n+1, n)的任一黑点都是 2 度点。
证： 且以`b_k`记度数为`k`的黑点数, 设黑点最大的度为`h`，由于`b_1=0`, 故黑点总数\[\begin{equation}n=b_2+b_3+b_4+\cdots+b_h \end{equation}\]遍历黑点来数边，可得\[\begin{equation}2n=2b_2+3b_3+4b_4+\cdots+hb_h\end{equation}\]`(2)-2\cdot(1)`得\[0=b_3+2b_4+\cdots+(h-2)b_{h-2}\] 所以               `\forall k>2, b_k=0 `,最后得`n=b_2`,即所有的黑点都是2度点。

mathe

m=n+2的情况也比较简单，正好一个黑点有三条边，而且三个分支中白点数目都严格小于n/2.
但是m=n+3就复杂一些了，有两种情况，一个四度黑点或两个三度黑点

hujunhua

mathe 发表于 2014-11-8 16:10
如果仅仅对给定的m,n计数，还是13#的方法会更加有效，但是需要改进。。。。

最大层数为 n+1。
每剥去一层，都使得各“终点站”到“终点站”的通路长度减少2，由于总是从两端向中间等速缩减，所以根结点是最长通路的中点。
为了得到最大的最长通路，n个黑点必须都在其上，间以2度白点，再加两端叶结点，通路上共计2n+1站，长度（边数）为2n。
其它白点皆叶结点，首次剥之，最长通路变为包含2n-1个结点的一字长蛇阵。
对于有最大的最长通路的树，当 n 为奇数时，根结点为黑点，当n为偶数时，根结点为白点。

有最大的最长通路的解也是一种极端解，因此也是唯一的。@mathe在4#给出的就是这种极端解。这就是它在29#的解序列中出现在末尾的原因。