如何判断一条边是否在某条路径上
How to tell if an edge is on some path
给定一个无向图 G=V,E，2 个顶点：x，y 和一条边 e，
我想检查是否有一条从 x 到 y 的路径包含给定的边 e。
我的想法：通过定义一个网络流来解决这个问题，其中 x 和 y 是源和汇，并检查 e 中的流是否大于 0，这意味着存在路径。
但是有两个问题：
- 我不知道如何指向边缘
- 每条边的容量是多少？
所以我猜这不是正确的方法...如果有人能提出想法那就太好了。
一种方法如下：
- 从 E(G) 中删除边 e = (u,v)。
- 如果任何 x-y 路径包含 e，则路径将是以下两种形式之一：(1) x *-> u -> v *-> y 或 (2) x *- > v -> u *-> y 其中 *-> 表示可达。使用此事实检查以下任一情况是否成立
2.1. x 可以从 u 到达，y 可以从 v 到达。
2.2. x 可以从 v 到达，y 可以从 u 到达。
我们可以使用 BFS 来找到可达性。
给定一个无向图 G=V,E，2 个顶点：x，y 和一条边 e，
我想检查是否有一条从 x 到 y 的路径包含给定的边 e。
我的想法：通过定义一个网络流来解决这个问题，其中 x 和 y 是源和汇，并检查 e 中的流是否大于 0，这意味着存在路径。 但是有两个问题：
- 我不知道如何指向边缘
- 每条边的容量是多少？
所以我猜这不是正确的方法...如果有人能提出想法那就太好了。
一种方法如下：
- 从 E(G) 中删除边 e = (u,v)。
- 如果任何 x-y 路径包含 e，则路径将是以下两种形式之一：(1) x *-> u -> v *-> y 或 (2) x *- > v -> u *-> y 其中 *-> 表示可达。使用此事实检查以下任一情况是否成立 2.1. x 可以从 u 到达，y 可以从 v 到达。 2.2. x 可以从 v 到达，y 可以从 u 到达。 我们可以使用 BFS 来找到可达性。