如何查找是否存在从顶点 x 到顶点 y 的包含边 e 的简单路径
How to find if there is a simple path from vertex x to vertex y that includes the edge e
所以我遇到了这个问题，希望有人能帮助我。
给定一个 无向 图 G = (V, E)，2 个顶点 x,y 和一条边 e = (v,u)。
建议一种算法来查找是否存在从 x 到 y 的包含边 e 的简单路径。
所以这里的重点是简单路径而不是常规路径，对于常规路径，使用BFS搜索从x到v的路径和从u到y的路径是一个简单的问题。
我知道这个问题可以使用最大流方法来解决，但我只是不知道如何构建一个可以在其上实现最大流算法的新图，所以它告诉我上面的标准是否是实现与否，希望得到帮助。
提前致谢。
不共享边（边无关）
您可以通过在 x 和 y 处使用 +1 源，在 u 和 v 处使用 -1 汇来求解最大流量。
删除边e，并将所有其他边设置为容量1。
一条从 x 到 y 通过边 e 的简单路径存在当且仅当你能在这个新的最大流问题中找到 2 的流。
不共享顶点（与顶点无关，即简单路径）
将原始图中的每个顶点v[i]拆分为两个顶点，a[i]和b[i]。
对于原始v[i]和v[j]之间的每个无向边，将有向边b[j]添加到a[i]和b[i]添加到a[j] 容量为 1.
还添加一条从 a[i] 到 b[i] 的有向边，每个顶点的容量为 1 v[i]。
这个想法是，流必须总是到达一个 a[i] 顶点，并从一个 b[i] 顶点离开，在从 a[i] 到 [=12] 穿过容量 1 瓶颈之后=].这样可以确保每个顶点只能使用一次。
使用这个新图，继续处理与边缘无关的情况。
所以我遇到了这个问题，希望有人能帮助我。
给定一个 无向 图 G = (V, E)，2 个顶点 x,y 和一条边 e = (v,u)。
建议一种算法来查找是否存在从 x 到 y 的包含边 e 的简单路径。
所以这里的重点是简单路径而不是常规路径，对于常规路径，使用BFS搜索从x到v的路径和从u到y的路径是一个简单的问题。
我知道这个问题可以使用最大流方法来解决，但我只是不知道如何构建一个可以在其上实现最大流算法的新图，所以它告诉我上面的标准是否是实现与否，希望得到帮助。
提前致谢。
不共享边（边无关）
您可以通过在 x 和 y 处使用 +1 源，在 u 和 v 处使用 -1 汇来求解最大流量。
删除边e，并将所有其他边设置为容量1。
一条从 x 到 y 通过边 e 的简单路径存在当且仅当你能在这个新的最大流问题中找到 2 的流。
不共享顶点（与顶点无关，即简单路径）
将原始图中的每个顶点v[i]拆分为两个顶点，a[i]和b[i]。
对于原始v[i]和v[j]之间的每个无向边，将有向边b[j]添加到a[i]和b[i]添加到a[j] 容量为 1.
还添加一条从 a[i] 到 b[i] 的有向边，每个顶点的容量为 1 v[i]。
这个想法是，流必须总是到达一个 a[i] 顶点，并从一个 b[i] 顶点离开，在从 a[i] 到 [=12] 穿过容量 1 瓶颈之后=].这样可以确保每个顶点只能使用一次。
使用这个新图，继续处理与边缘无关的情况。