通过删除一条边将树分成相等的部分

Question

我正在寻找一种算法，可以通过移除一条边来分割具有N个节点的树（每个节点的最大度数为3），以使得结果产生的两棵树尽可能接近N/2。如何找到“最中心”的边？

该树作为算法的前一个阶段的输入，并且作为图形输入 - 因此它既不平衡也不清楚哪个节点是根。

我的想法是在树中找到最长路径，然后选择最长路径中间的边。这样行得通吗？

最理想的情况下，我希望找到一种解决方案，可以确保两棵树都不超过2N / 3个节点。

感谢您的回答。

- Michal Ferko

---

如果您没有关于树的布局平衡的数据，可以从一个退化的树开始（例如，在左侧分支放置100个，在右侧分支放置50个），最终得到一个50/100的分裂，回到同样的情况。 - Marc B

是的，但是选择长度为150的最长路径并取中间边（路径上第75或76条边）将其分成相等的部分。问题是这样一个最优边是否总存在（我认为不会）。 - Michal Ferko

退化树基本上就是一个链表。例如，唯一具有两个子节点的节点是根节点。因此，您可以从根节点通过树的两条路径。向左下方有100个线性节点，向右下方有50个节点。将最长的路径（100个节点的分支）拆分为50/50，再加上右侧分支中的余数，这样您就将树从100/50转换为50/100。 - Marc B

抱歉，我觉得你误解了我的意思。输入实际上是一个具有非定向边的图，这意味着我想要找到的最长路径是“两个节点之间的最大可能距离”。在一般图中找到最长路径是NP完全问题。但是输出图的算法被设计为始终是一棵树（不是树数据结构而是树形图）。 - Michal Ferko

我不相信你的算法是正确的。考虑一棵完全平衡的三叉树，其节点链条长达根节点。在这种情况下，取最长路径并在中点处剪断将会给你完整的三叉树和一个简单的链表。与链表相比，该树将会有指数级别更多的节点。 - templatetypedef

显然是作业。我很失望，SO。 - Per

Answer 1

我认为你在评论中提到的原始算法不能工作。然而，我认为您可以使用修改过的DFS算法以O（n）时间和空间解决此问题。

首先遍历图以计算总节点数，将其称为n。 现在选择一个任意节点并以其为根节点。 我们现在将从根开始递归地探索树，并计算每个子树中有多少节点。 可以使用简单的递归完成以下操作：

- 如果当前节点为空，则返回0。 - 否则： - 对于每个子代，计算根据该子代确定的子树中的节点数。 - 返回1 +所有子树中节点总数。

此时，我们知道了通过删除该边将得到什么样的分裂情况，因为如果该边下面的子树具有k个节点，则拆分将为（k，n-k）。 因此，您可以通过迭代所有节点并查找最平衡（k，n-k）的节点来找到最佳切割点。

计算节点需要O（n）时间，运行递归最多访问每个节点和边O（1）次，因此也需要O（n）时间。 查找最佳切割需要额外的O（n）时间，因此净运行时间为O（n）。由于我们需要存储子树节点计数，因此还需要O（n）内存。

希望这可以帮助您！

- templatetypedef

---

你无法找到任何算法来完成这个任务。 - Saeed Amiri

@SaeedAmiri- 抱歉，你能详细解释一下吗？ - templatetypedef

是的，这个可以工作。谢谢。我曾考虑过在边缘的一侧和另一侧计算节点数，但简单的方法将会是O(n^2)。你的算法是线性的，非常好。再次感谢。 - Michal Ferko

非常好的算法。一个备注：计算顶点的第一部分是不必要的，因为在第二部分完成后，我们也有树中顶点的数量。 - tommsch

Answer 2

如果你看过我对树的分治算法的回答，你会发现我会找到一个将树分成两个近乎相等大小的子树的节点（自底向上的算法），现在你只需要选择这个节点的其中一条边来实现你想要的功能。

你当前的方法不起作用，假设你有一棵完全二叉树，现在在其中一个叶子节点上添加一条长度为3*log n的路径（将其命名为bad叶子节点），你的最长路径将在其他叶子节点中的一条路径上，连接到这个bad叶子节点的路径的末端，而你的中间边将在这条路径上（事实上，在你经过坏叶子节点之后），如果你基于这条边进行分区，你将得到一个O(log n)大小的部分和一个O(n)大小的部分。

- Saeed Amiri