如何查找是否存在从顶点 x 到顶点 y 且包含边 e 的简单路径

Question

所以我面临这个问题，我希望有人可以帮助我。

给定一个无向图 G = (V, E)、2 个顶点 x,y 和一条边 e = (v,u)。

提出一种算法来查找是否存在从 x 到 y 且包含边 e 的简单路径。

所以这里的重点是简单路径而不是常规路径，对于常规路径来说，使用 BFS 搜索从 x 到 v 的路径和从 u 到 y 的路径是一个简单的问题。

我知道可以使用最大流方法解决问题，但我只是不知道如何构建一个可以在其上实现最大流算法的新图，以便它告诉是否达到上述标准，我希望得到帮助。

提前致谢。

Answer 1

不共享边（边无关）

您可以在 x 和 y 处使用 +1 源，在 u 和 v 处使用 -1 汇来求解最大流量。

删除边 e，并将所有其他边设置为容量 1。

当且仅当您可以在这个新的最大流问题中找到流为 2 时，存在一条通过边 e 从 x 到 y 的简单路径。

v[i]将原始图中的每个顶点拆分为两个顶点，a[i]和b[i]。

对于原始图像中v[i]和之间的每个无向边，将有向边添加到和到，容量为 1。v[j]b[j]a[i]b[i]a[j]

还为每个顶点添加一条从a[i]到且容量为 1 的有向边。b[i]v[i]

这个想法是，流必须始终到达一个a[i]顶点，并b[i]在从到穿过容量为 1 的瓶颈后从a[i]顶点离开b[i]。这确保每个顶点只能使用一次。

使用这个新图，继续处理与边缘无关的情况。