3

给定 G = (V,E) 中的两个顶点 u 和 v 以及一个正整数 k，描述一个算法来判断是否存在从 u 到 v 的不相交边路径。如果决策问题的答案是肯定的，描述如何计算一组 k 边不相交的路径。

解决方案：运行从 u 到 v 的最大流（给图 G 中的所有边的权重为 1，以便一条边只能是从 u 到 v 的一条路径的一部分）并获得流的值。如果流的值为 k，那么我们对决策问题的答案是肯定的。

现在为了找到所有这样的路径，通过从 u 执行 BFS 来找到最小切割，因此我将拥有顶点分区，这会将顶点分成 2 个集合，每个集合在最小切割的每一侧。

然后我是否需要再次执行从 u 到 v 的 DFS，以查找仅具有这些顶点的所有路径，这些顶点存在于我从最小切割中获得的两个分区集中。

还是有其他更清洁的方法？得到所有k条边不相交的路径。

4

1 回答 1

4

获得流程后，您可以按照流程提取边缘不相交的路径。

起始节点将有一个 k 流，沿着 k 条边离开 u。

对于这些边中的每一个，您可以继续沿流出流的方向移动以提取路径，直到到达 v。您需要做的就是标记您已经使用过的边以避免重复边。

对 k 个流单元中的每一个重复，留下 u 以提取所有 k 个路径。

伪代码

repeat k times:
  set x to start node
  set path to []
  while x is not equal to end node:
      find a edge from x which has flow>0, let y be the vertex at the far end
      decrease flow from x->y by 1 unit
      append y to path
      set x equal to y
  print path
于 2016-04-27T20:36:52.223 回答