如何通过添加最少数量的边来增加图中min-cut（最小割）的大小

Question

问题：给定一棵树 T = (V,E)。添加最少数量的边，即使从新创建的图中删除一个边仍然存在从任何顶点到任何其他顶点的路径。

我认为这个问题可以简化为将图的 min-cut 大小从当前的 1 增加到 2。但是，如何高效地实现这样的算法呢？

- Abhinav Batra

---

另一种描述它的方式是添加边来创建无桥图。作为起点，只考虑叶节点之间的边就足够了。 - Nabb

仅在叶节点之间添加边并不能保证最小割的大小至少为2。 - Abhinav Batra

Answer 1

这里是一个算法，可解决任何无向图的问题。在一些简化后，它也可应用于树（步骤1不需要）。

1. 使用DFS或Robert Tarjan的桥梁查找算法，找出图中的所有桥。
2. 创建一个图（实际上是一棵树），其中每个无桥子图都被替换为一个单独的顶点。
3. 将树中的每条链路折叠成一条边。
4. 找到两个叶子节点之间的路径（如果可能，则长度至少为3）。
5. 选择原始图中与此路径两端相对应的任意两个顶点，并将它们连接起来。
6. 将此路径折叠成单个顶点。
7. 只要树中还有多于一个顶点，就从步骤3重复。

步骤4保证我们不会在步骤6后得到新的不必要的叶子节点，这是优化的关键。

- Evgeny Kluev

---

这是一个很棒的解决方案，与我想到的方法非常不同。已点赞。 - krjampani

Answer 2

Evgeny的解决方案非常好，但这里有一个更简单的解决方案适用于树，并且其正确性易于理解。

设L为树T的（原始）叶子。让n成为树中的任何节点，使得通过去除n而获得的每个子树都至多拥有|L|/2个原始叶子。请注意，总是可以找到这样的节点n。

让T₁，T₂，..，T_k成为通过去除n而获得的子树。每个原始叶子（在L中）存在于T_i之一中。从原始叶子中构造最大不相交对，约束条件是任何一对中的两个原始叶子属于不同的子树。（这在概念上与在完整的k-部分图中构造最大匹配相同，其中部分是存在于子树中的原始叶子。）

如果 |L| 是偶数，则每个原始叶子节点都会出现在某个对中，并且添加与这些对应的边将使得结果图形成为2-连通。因此，在这种情况下，我们需要添加 |L|/2 条边。

如果 |L| 是奇数，则一个原始叶子节点将不会成对出现，因此我们可以将该叶子节点连接到存在于不同子树中的任意原始叶子节点。在这种情况下，我们需要添加 (|L|+1)/2 条边。

- krjampani