什么是节点不相交路径？

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 被称为 node-disjoint 如果 v_i != u_j 对于任何有效的 i 和 j。

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

Answer 2

你也可以认为每个顶点都有自己的容量，也就是说每个顶点只能被传递一次。以这种方式构建一个新图：
(1)容量(vi) = 1
(2)容量(ei) = 1
然后 运行 最大流量。答案是最大数量。