图论
我正在尝试为树写一个分而治之的算法。 对于除法步骤，我需要一种算法，通过删除一个节点 ，将给定的无向图G =（V，E）与n个节点和m个边分割成子树。 所有的子图应该具有它们不包含多于n / 2个节点的属性（树应该尽可能地相等）。 首先，我尝试从树中递归地移除所有叶子以找到剩余的最后一个节点，然后尝试在G中找到最长的路径并移除它的中间节点。 下面给出的图表显示这两种方法都不起作用：
是否有一些工作算法可以做我想做的事（在上面的例子中返回节点H）。
我想你可以用这样的算法来做到这一点：
从根开始（如果树没有根，请选择任何节点）。
在每一步中，尝试下降到具有最大子树的子节点（节点数量在“最小”之下）。
如果这样做会使“高于”节点的数量大于n / 2，请停止，否则继续使用该小孩。
如果树合理平衡并且我们为每个节点预先计算了子树的大小，那么该算法应该是O（log n）。 如果其中一个条件不适用，那就是O（n）。
一个确切的算法是这样的，
从叶子开始，创造不相交的曲线图（其实都是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）in如果列表大小等于或大于n / 2，则选择相关的好节点。 （实际上在满足这个条件的最小列表中找到好节点）。
显而易见的是，如果可以很好地划分树（每个部分至多有n / 2个节点），则可以通过该算法来完成，但如果不是这样的话（事实上，您不能将它分成两部分或更多部分尺寸小于n / 2），这给你一个很好的近似值。 同样如你所见，在输入树中没有任何假设。
注意：我不知道可能有一棵树，因此通过删除一个节点不可能将它分割成小于n / 2的部分。
这个问题看起来类似于找到一个物体的质心。 假设每个节点都是等质量（重量）的点质量，其位置由图中的位置给出。 你的算法试图找出质量中心，即所有连接的子树中具有相似累计节点权重的节点。
您可以计算每个节点的所有子树的累加权重。 然后选择一个最平衡的，没有子树重量超过n/2 。 可能这是一些动态编程的任务。
上一篇: graph theory