在 运行 最大流算法之后,在流网络中找到所有在某个最小切割中的边
After running a max flow algorithm, find in a flow network all edges that are in some min-cut
设 G=(V,A,s,t,U) 为流网络。假设我们已经获得了最大流量。有没有一种快速算法可以找到某个最小切割中的所有边?
我知道如果x
是最大流,那么我们可以在残差网络G(x)
中找到从源s
可达的顶点集合S
,以及 T
我们可以到达 t
的顶点集。因此,S
及其补码是最小割。此外,T
和它的补集也形成了一个最小割。
如果不幸的是 T
不是 S
的补集,则最小割不是唯一的。我想知道是否有一种好的方法来确定末端既不在 S
也不在 T
的边缘是否属于最小切割。
每个圆弧 u-->v
属于某个 s--t
min cut 当且仅当
- 没有从
u
到t
, 的剩余路径
- 没有从
s
到v
的剩余路径,并且
- 没有从
u
到v
的剩余路径。
为了证明 if 方向,考虑由残差路径从 s
或 u
可达的顶点组成的切割,即 s--t
由 (1) 切割,具有剩余容量为零,因此是 s--t
最小构造削减,并且包含 u-->v
由 (2) 和 (3)。
为了证明唯一的方向,我们可以使用包含 u-->v
的 s--t
最小切割来证明,对于从 u
到 t
的每条路径,从s
到v
,或从u
到v
,路径中的某些弧是非残差的。
这会让您很容易地到达 O(n m)
时间。也许这就足够了——如果还不够好,有一篇关于回答离线可达性查询的文献可能会有用。
设 G=(V,A,s,t,U) 为流网络。假设我们已经获得了最大流量。有没有一种快速算法可以找到某个最小切割中的所有边?
我知道如果x
是最大流,那么我们可以在残差网络G(x)
中找到从源s
可达的顶点集合S
,以及 T
我们可以到达 t
的顶点集。因此,S
及其补码是最小割。此外,T
和它的补集也形成了一个最小割。
如果不幸的是 T
不是 S
的补集,则最小割不是唯一的。我想知道是否有一种好的方法来确定末端既不在 S
也不在 T
的边缘是否属于最小切割。
每个圆弧 u-->v
属于某个 s--t
min cut 当且仅当
- 没有从
u
到t
, 的剩余路径
- 没有从
s
到v
的剩余路径,并且 - 没有从
u
到v
的剩余路径。
为了证明 if 方向,考虑由残差路径从 s
或 u
可达的顶点组成的切割,即 s--t
由 (1) 切割,具有剩余容量为零,因此是 s--t
最小构造削减,并且包含 u-->v
由 (2) 和 (3)。
为了证明唯一的方向,我们可以使用包含 u-->v
的 s--t
最小切割来证明,对于从 u
到 t
的每条路径,从s
到v
,或从u
到v
,路径中的某些弧是非残差的。
这会让您很容易地到达 O(n m)
时间。也许这就足够了——如果还不够好,有一篇关于回答离线可达性查询的文献可能会有用。