问题:给定一棵树 T = (V,E)。添加最少数量的边,即使从新创建的图中删除一个边仍然存在从任何顶点到任何其他顶点的路径。
我认为这个问题可以简化为将图的 min-cut 大小从当前的 1 增加到 2。但是,如何高效地实现这样的算法呢?
我认为这个问题可以简化为将图的 min-cut 大小从当前的 1 增加到 2。但是,如何高效地实现这样的算法呢?
Evgeny的解决方案非常好,但这里有一个更简单的解决方案适用于树,并且其正确性易于理解。
设L
为树T
的(原始)叶子。让n
成为树中的任何节点,使得通过去除n
而获得的每个子树都至多拥有|L|/2
个原始叶子。请注意,总是可以找到这样的节点n
。
让T
1,T
2,..,T
k成为通过去除n
而获得的子树。每个原始叶子(在L
中)存在于T
i之一中。从原始叶子中构造最大不相交对,约束条件是任何一对中的两个原始叶子属于不同的子树。(这在概念上与在完整的k-部分图中构造最大匹配相同,其中部分是存在于子树中的原始叶子。)
|L|
是偶数,则每个原始叶子节点都会出现在某个对中,并且添加与这些对应的边将使得结果图形成为2-连通。因此,在这种情况下,我们需要添加 |L|/2
条边。|L|
是奇数,则一个原始叶子节点将不会成对出现,因此我们可以将该叶子节点连接到存在于不同子树中的任意原始叶子节点。在这种情况下,我们需要添加 (|L|+1)/2
条边。