最大流量 - 通过顶点 - 如何实现？

Question

问题：

假设 G = (V, E) 是一个包含n >= 3个顶点和m条边的有向图。顶点集 V 包括三个特殊顶点 a、v 和 b。如果存在从 a 到 b 的简单路径（即不包含重复顶点的路径），则找出通过 v 的这条路径。我认为可以使用最大流算法来解决这个问题，但我不确定如何实现。它让我想起了带有多个源的最大流算法，其中边的容量为1。有人知道怎样将此问题转化为最大流算法吗？

如果我将顶点 b 设为汇点，则无法确保路径中是否包含 v。如果我将 v 设为汇点，到达 v 后该如何继续呢？

- Mads Andersen

---

v 只是到 b 的第二条路径的源头吗？ - Mikeb

你可以在谷歌上尝试搜索“最大流下界”。如果你强制通过顶点v的最小流量为1，那么你本质上就有了一个通过v的路径。 - phimuemue

@Mikeb 我不这么认为。从 a->v 的流可能是一条使得从 v-b 流动变得不可能的路径，我认为。 - Mads Andersen

@phimuemue- 这可能不会正常工作，因为图中可能存在一个循环，并且流量下限可能只会通过 v 路由流量，而该流量循环与从 a 到 b 的流路径没有任何连接。 - templatetypedef

@bobjink：针对这种流问题，有一些算法可以解决——然而，正如templatetypedef所指出的那样，这可能根本行不通... - phimuemue

Answer 1

以下应该有效：

• 找到从a到v的所有最小路径，这些路径不包含顶点b。您可以通过在不包括顶点b的图上进行DFS（例如）来获得它们。我们说一个a-v路径p是最小的，如果没有其他a-v路径p'仅包含来自p的顶点。

• 对于每个最小的a-v路径，尝试查找一条从v到b的路径，请忽略已经属于a-v路径的顶点。如果您找到这样的东西，那就完成了。

备注：请注意，路径数量可能会呈指数增长，但正如我在评论中指出的那样，至少这个问题的广义版本似乎可以降低到TSP，因此可能非常困难。

- phimuemue

---

这也是我能找到的唯一解决方案。不是我希望得到的答案:/ - Mads Andersen

Answer 2

这相当于询问一个图是否包含一个有向路径的子图同构，该路径有三个顶点（模式是输入图中某些顶点上的图形，如果模式的边可以映射到子图的简单、成对顶点不交路径上，则子图是同构于模式的）。Fortune, Hopcroft, and Wyllie已经证明，对于几乎所有固定模式，包括这个模式，有向子图同构是NP难问题。因此，该问题是NP难问题，除非P = NP，否则不能通过流技术来解决。

然而，无向版本可以通过将a和b作为源，v作为汇聚来缩小到最大流问题。

- Falk Hüffner