给定 G = (V,E) 中的两个顶点 u 和 v 以及一个正整数 k,描述一个算法来判断是否存在从 u 到 v 的不相交边路径。如果决策问题的答案是肯定的,描述如何计算一组 k 边不相交的路径。
解决方案:运行从 u 到 v 的最大流(给图 G 中的所有边的权重为 1,以便一条边只能是从 u 到 v 的一条路径的一部分)并获得流的值。如果流的值为 k,那么我们对决策问题的答案是肯定的。
现在为了找到所有这样的路径,通过从 u 执行 BFS 来找到最小切割,因此我将拥有顶点分区,这会将顶点分成 2 个集合,每个集合在最小切割的每一侧。
然后我是否需要再次执行从 u 到 v 的 DFS,以查找仅具有这些顶点的所有路径,这些顶点存在于我从最小切割中获得的两个分区集中。
还是有其他更清洁的方法?得到所有k条边不相交的路径。