1

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

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

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

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

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

4

1 回答 1

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 来查找可达性。
于 2017-01-31T17:21:44.297 回答