樹木的分治算法

Question

我想爲樹木編寫一個分治&征服算法。對於除法步驟，我需要一種算法，通過刪除節點將具有n個節點和m個邊的給定無向圖G =（V，E）劃分爲子樹。所有子圖應該具有它們不包含多於n/2節點的屬性（樹應儘可能相等）。首先，我嘗試從樹中遞歸地移除所有葉子以找到剩餘的最後一個節點，然後嘗試在G中找到最長的路徑並移除它的中間節點。下面給出的圖表顯示，這兩種方法不起作用：

有一些工作的算法，我想要做什麼（在上述情況下返回節點H）。

Answer 1

我想你可以用這樣的算法做到這一點：

開始在根（如果樹的根源並非是，挑選任何節點）。
在每個步驟中，嘗試下降到具有最大子樹的子節點（節點數量低於最大）。
如果這樣做會使「高於」節點的數量大於n/2，請停止，否則繼續使用該子節點。

如果樹合理平衡並且我們爲每個節點預先計算了子樹的大小，那麼此算法應該爲O（log n）。如果其中一個條件不適用，那就是O（n）。

Answer 2

一個確切的算法是這樣，

從葉子開始，創造不相交的曲線圖（其實都是K1），在每一步找到這個葉子的父母，並把它們合併成新的樹，在每一步如果節點x有r已知的兒童和節點的程度j這樣j = r+1，只是這是不是在x子節點的節點是在這種情況下，當前節點的父說節點x是nice，否則，也有一些孩子這樣那些相關的有根子樹未構建，在這種情況下，我們說節點x是bad。

因此，在每一步nice節點連接到其相關的父，這是顯而易見的每一步需要sum of {degree of parent nice nodes}也在每一步，你至少有一個很好的節點（因爲你從葉開始），所以算法是O（n） ，並且它會完全完成，但是爲了找到應該被刪除的節點，實際上在每個步驟中都需要檢查一個dijoint列表的大小（子樹列表），這可以在O（1）中完成，同樣如果列表大小等於或大於n/2，然後選擇相關的好節點。 （實際上在滿足這個條件的最小列表中找到好節點）。很明顯的一點是，如果可以很好地劃分樹（每個部分至多有n/2個節點），那麼你可以用這個算法來完成，但是如果不是這樣的話（實際上你不能把它分成兩部分或者小於n/2的更多部分），這給你很好的近似值。同樣如你所見，在輸入樹中沒有任何假設。

注意：我不知道是否有可能有一棵樹，因此不可能通過刪除一個節點將它分割成小於n/2的部分。

Answer 3

此問題看起來類似於找到對象的center of mass。 假設您的每個節點都是等質量（重量）的點質量，其位置由圖中的位置給出。您的算法會嘗試查找質心，即所有連接的子樹中具有類似累計節點權重的節點。

您可以計算每個節點在所有子樹上的累加權重。然後選擇最平衡的那個，s.t.沒有子樹的重量超過n/2。可能這是一些動態編程的任務。