algorithm - 如何判断边缘是否在某个路径上

Question

给定一个无向图 G=V,E, 2 个顶点：x, y 和边 e，

我想检查是否有一条从 x 到 y 的路径包含给定的边 e。

我的想法：通过定义一个网络流来解决这个问题，其中 x 和 y 是源和汇，并检查 e 中的流是否大于 0，这意味着存在路径。但是有两个问题：

1. 我不知道如何指向边缘
2. 每个边缘的容量是多少？

所以我猜这不是正确的方法......如果有人能给出一个想法，那就太好了。

Answer 1

一种方法可能如下：

1. 从 E(G) 中删除边 e = (u,v)。
2. 如果任何 xy 路径包含 e，则该路径将是以下两种形式之一：(1) x *-> u -> v *-> y 或 (2) x *-> v -> u *-> y其中 *-> 表示可达。使用这个事实来检查以下任何一种情况是否成立 2.1。x 可从 u 访问，y 可从 v.2.2 访问。x 可从 v 到达，y 可从 u 到达。我们可以使用 BFS 来查找可达性。