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

问题：最大流量 - 通过顶点 - 如何？

设G =（V，E）是n> = 3个m边的顶点的有向图。顶点集合V包括三个特殊顶点a，v和b。如果存在，则通过v找到从a到b的简单路径。（一个简单的路径是没有重复顶点的路径）

我相信这个问题应该可以用Max Flow算法解决，但我不知道如何。它让我想起了一个Max Flow算法，该算法具有多个来源，其中边缘具有容量1.任何人都知道如何将问题简化为最大流量算法？

如果我将顶点b设置为接收器，我不能确定它将包含v。如果我将v设置为接收器，当达到v时我该如何继续？

来源

2012-01-04 Mads Andersen

不会只是b的第二条路径的来源吗？ – Mikeb 2012-01-04 21:23:41

你可以尝试谷歌的“最大流量下限”。如果你强制顶点v的最小流量为1，那么你基本上有一条通过v。 – phimuemue 2012-01-04 21:33:55

@Mikeb的路径我不这么认为。从a-> v的流动可能是一条路径，使我不可能从v-b流出一个流。 – 2012-01-04 21:43:34

下面应该工作：

找到所有最小路径从a到v，那不包含顶点b。您可以通过（例如）图形上的DFS获取这些顶点，但不包含顶点b。我们说a-v -path p是最小的，如果没有其他a-v -path p'只包含来自p的顶点。
每个最小a-v -path，试图找到从v到b忽略顶点已经属于a-v -path的路径。如果你发现这样的事情，你就完成了。

注：注意路径的数量可能会增长指数，但正如我在我的评论中指出，至少在这个问题的通用版本似乎是还原到TSP，因而是可能很难。

来源

2012-01-04 22:22:17 phimuemue

这也是我能找到的唯一解决方案。不是我所希望的答案：/ – 2012-01-04 22:31:17

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

尽管可以通过让a和b成为源代码并使用接收器，但可以将无向版本降低到最大流量。

来源

2012-01-07 11:49:17

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

回答

相关问题