有向图的闭包--最大闭包问题

Question

我正在阅读这篇维基文章：https://en.wikipedia.org/wiki/Closure_problem和我有几个问题。

首先，本文指出“有向图的闭包是一组顶点C，因此没有边离开C”。假设我有一个图G=(V，E)，其中V= {a，b，c}和E={(a，b)，(b，c)，(a，c)}。然后，根据闭包的定义，闭包C(G) = {b，c}，因为没有离开C.的边。

然而，在算法部分下的最大流段的

1. 中，它指出“割集的同一侧的顶点集自动形成闭包C”，边的图表示C={s,1,5,3,2}。但是，很明显，有一些边从闭包中出来，例如边(2，t)，(s，7)。

那么，我在这里没有正确理解什么呢？谢谢!

Answer 1

将顶点s和t相加到初始图中，发现的最小割集是初始图中的闭包，而不是修改后的图中的闭包。该算法在很大程度上依赖于最大流最小切割定理.显然存在一个有限割集，例如，用{s}切，其他的一切都是有限的。因此，最小割集也是有限的，这意味着它不可能有无限的边，并且初始图中的所有边都是无限的。随后，修改图中的最小割集也是初始图中的闭包.