algorithm - 计算最小可能的树

Question

给定一组节点，我如何构造一棵树，以最小化max(max(degree), max(depth))的方式将所有节点连接在一起？

例如，给定一组五个节点，我可以像这样连接它们:

但是，这不是最小值，因为 max(degree) == 4 和 max(depth) == 1，更好的树应该是:

它有 max(degree) == 2 和 max(depth) == 2

编辑:算法不一定要快，但计算出绝对最优的树很重要。

Answer 1

从相反的方向走。给定度数和深度，最大节点数是总和 = 1 + 度数 + 度数^2 + ... + 度数^深度。这是整数序列 A031973 .您可以每次都计算它，或者只存储第一剂量的值。无论哪种情况，您都搜索大于节点数的最小值，并找出相应的 D=degree=depth

当你知道你的 D 时，就可以按照你喜欢的方式填充树，关于它的边界。