計算最小的可能樹

Question

給定一組節點，如何構造一棵樹，以最小化最大（max（度），max（深度））的方式將所有節點連接在一起？

例如，給定一組五個節點的，我可以將它們連接起來，像這樣：

然而，這不是最小的，因爲最大（度）== 4和max（深度） == 1，更好的樹將是：

具有最大（度）== 2和max（深度）== 2

編輯::算法不一定要快，但計算絕對最佳的樹很重要。

Answer 1

從相反的方向走。給定度數和深度，節點的最大數量是和= 1 +度+度^ 2 + ... +度^深度。這是整數序列A031973。您可以每次計算一次，或者只存儲第一批值。無論是哪種情況，您都會搜索最大值，並且計算出您的節點數量，然後找出相應的D =度數=深度

當您知道您的D時，只需按照您喜歡的方式填充樹，就其邊界而言。

Answer 2

具有深度==度的樹中節點的最大數量是n = Sum degree^k（k = 0到1）。事實上，總和是一個幾何系列。因此它的值等於（degree^degree-1）/（degree-1），這可能要快得多。 （儘管速度沒有關係;-)） 但是，您不能以代數方式求解方程式n =（degree^degree-1）/（degree-1），因此您必須存儲總和的預先計算值，然後選擇產生最小可能值的程度值仍然大於/等於n。