3

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

我相信问题可以简化为将图的最小切割的大小从当前的最小切割 1 增加到 2。但是这样做的有效算法是什么。

4

2 回答 2

2

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

  1. 使用 DFS 或Robert Tarjan 的 Bridge-finding 算法查找图中的所有桥梁。
  2. 创建一个图（实际上，它是一棵树），其中每个无桥子图都替换为单个顶点。
  3. 将树中的每条链折叠成一条边。
  4. 在两片叶子之间找到一条路径（如果可能，长度至少为 3）。
  5. 在原图的子图中选取任意两个顶点，对应于这条路径的两端，并将它们连接起来。
  6. 将此路径折叠成一个顶点。
  7. 当树中有多个顶点时，从第 3 步开始重复。

第 4 步保证在第 6 步之后我们不会得到一个新的不需要的叶子，这是优化的关键。

于 2012-10-06T09:14:18.450 回答
1

Evgeny 的解决方案非常好，但这里有一个更简单的解决方案，适用于 Trees，其正确性很容易看出。

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

令T1 , T2 , .. , Tk为移除 得到的子树n。每个原始叶子 (in L) 都存在于其中一个Ti中。从原始叶子构造最大不相交对，约束条件是任何对中的两个原始叶子属于不同的子树。（这在概念上与在完整的 k 部分图中构建最大匹配相同，其部分是子树中存在的原始叶子）。

如果|L|是偶数，那么每个原始叶子都将出现在某个对中，并且添加与这些对中的每一个相对应的边将使结果图 2 连通。所以在这种情况下我们需要添加|L|/2边。

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

于 2012-10-06T16:20:08.760 回答