所以我面临这个问题，我希望有人可以帮助我。
给定一个无向的图 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。
当且仅当您可以在这个新的最大流问题中找到流为 2 时，存在一条通过边 e 从 x 到 y 的简单路径。
不共享顶点（顶点无关，即简单路径）
分割每个顶点v[i]在原始图中分成两个顶点，a[i] and b[i].
对于之间的每个无向边v[i] and v[j]在原来的情况下，添加有向边b[j] to a[i] and b[i] to a[j]容量为1。
还添加一条有向边a[i] to b[i]每个顶点的容量为 1v[i].
这个想法是流量必须始终到达一个a[i]顶点，并从 a 离开b[i]顶点，经过容量 1 瓶颈后a[i] to b[i]。这确保每个顶点只能使用一次。
使用这个新图，继续处理与边缘无关的情况。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
