树木的分治算法

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。可能这是一些动态编程的任务。