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_j 对于任何有效的 i 和 j。

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