什么是节点不相交路径？

Question

我需要解释什么是节点不相交的路径？以及如何确定有向图中两个节点Source和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

我们可以通过将每个顶点（源和目标除外）分成两个，从第一个副本到第二个副本添加一条边，重定向在此结束的所有边，来减少边缘不相交路径的最大数量顶点到第一个副本，第二个副本的所有传出边。之后，答案就是该图中的最大流量（所有边都应具有单位容量）。