如何确定从顶点 x 到顶点 y 是否存在包括边 e 的简单路径

Question

6

我遇到了这个问题，希望有人能够帮助我。

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

请提供一种算法，以查找是否存在一条包括边 e 的从 x 到 y 的简单路径。

因此，重点在于简单路径而不是普通路径。对于普通路径，可以使用广度优先搜索（BFS）从 x 搜索到 v 的路径和从 u 搜索到 y 的路径来解决问题。

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

谢谢您的帮助。

- Mohamad S.

2

普通的BFS实现是否会找到非简单路径并陷入循环中？ - clwhisk

1

@clwhisk，您可以删除边e，并使用BFS从x到v和从u到y找到一条路径。请注意，BFS将找到一条简单的路径，这可以被证明，我假设您已经在讲座中证明了它。因此，对于查找常规路径的问题，只需执行上述操作，路径将为(x→…→v→u→…→y)。 - Mohamad S.

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Peter de Rivaz · Accepted Answer

不共享边（独立边）

可以在x和y处添加+1源，并在u和v处添加-1汇解决最大流问题。

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

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

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

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

对于每个顶点v[i]，还要添加从a[i]到b[i]的容量为1的有向边。

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

有了这个新图，就像独立边的情况一样进行处理。