algorithm - 什么是节点不相交路径？

Question

我需要解释究竟什么是节点不相交的路径？以及如何确定有向图中两个节点 Source(s) 和 Sink(t) 之间的节点不相交路径的最大数量。任何人都可以用图形解释。

Answer 1

路径是顶点序列：s, v_1, .., v_m, t. 如果对于任何有效的和，则两条路径s, v_1, .., v_m, t和s, u_1, ..., u_k, t称为节点不相交。v_i != u_jij

我们可以通过将每个顶点（源和目标除外）一分为二，将第一个副本中的一条边添加到第二个副本中，重定向所有以此结尾的边，将这个问题简化为找到最大边不相交路径数第一个副本的顶点和第二个副本的所有出边。之后，答案就是这个图中的最大流量（所有边都应该有一个单位容量）。

Answer 2

您也可以认为每个顶点都有自己的容量，这意味着每个顶点只能通过一次。以这种方式构建一个新图：
(1)capacity(vi) = 1
(2)capacity(ei) = 1
然后运行最大流量。答案是最大数量。