删除树中的一个节点，使得森林中剩余树的 none 包含超过一半的节点

Question

让我们考虑一棵树（无环连通图），其中我们有 N 个顶点和 N-1 条边。我们如何找到是否存在一个节点，以便将其从树中移除将使森林中剩余的树的节点最多为所有节点的一半。如果真的存在，我们怎么知道是哪一个呢？

Answer 1

我相信这可以通过从叶子开始向上遍历图表并计算每个子树的数量来实现 - 如果完成而没有到达 N/2 那么你已经找到了你的节点。

考虑以下伪代码。

set v.count = 0 for all nodes
nodes = all leafs in graph
while true:
    nextStep = new set
    for each v in nodes:
        if v.count < N/2:
            parent = v.parent
            parent.count += v.count + 1 // add another child 
            nextStep.push(parent) // notice that if he exist the new one override
    if nextStep empty:
        break  
    nodes = nextStep // updating with the new set

在所有节点（DFS 或其他）上完成此遍历后 - 如果您仍然有未访问的节点（如 v.count==0），则不存在可按要求破坏树的节点.如果所有节点都访问过，那么选择计数最高的节点并删除他将实现您的目标。

希望有所帮助！

删除树中的一个节点，使得森林中剩余树的 none 包含超过一半的节点

Remove a node in a tree such that none of the remaining trees in the forest contain more than half of the nodes

tree

graph-theory