我遇到了这个问题,希望有人能够帮助我。
给定一个无向图 G = (V, E),两个顶点 x 和 y,以及一条边 e = (v, u)。
请提供一种算法,以查找是否存在一条包括边 e 的从 x 到 y 的简单路径。
因此,重点在于简单路径而不是普通路径。对于普通路径,可以使用广度优先搜索(BFS)从 x 搜索到 v 的路径和从 u 搜索到 y 的路径来解决问题。
我知道可以使用最大流方法解决此问题,但我不知道如何构建一个新的图,使其能够在上面实现最大流算法,以判断是否达到上述标准,希望得到帮助。
谢谢您的帮助。