问题:给定一棵树 T = (V,E) 。添加最小数量的边，以便即使从新创建的图中删除一条边，仍然存在从任何顶点到任何其他顶点的路径。
我相信这个问题可以减少到将图的最小切割的大小从当前的最小切割 1 增加到 2。但是这样做的有效算法是什么。
最佳答案
这是算法，可以解决任何无向图的这个问题。经过一些简化后，它可以应用于树(不需要第 1 步)。
- 使用 DFS 或 Bridge-finding algorithm by Robert Tarjan 查找图中的所有桥.
- 创建一个图(实际上，它是一棵树)，其中每个无桥子图都用一个顶点代替。
- 将树中的每条链折叠成一条边。
- 找到两片叶子之间的路径(如果可能，长度至少为 3)。
- 在原图的子图中任意选取两个顶点，对应这条路径的两端，并将它们连接起来。
- 将这条路径折叠成一个顶点。
- 当树中有多个顶点时，从第 3 步开始重复。
第 4 步保证我们不会在第 6 步之后得到不需要的新叶子，这是优化的关键。
关于algorithm - 如何通过添加最小边数来增加图中最小切割的大小，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/12757476/