I'm reading this wiki article: https://en.wikipedia.org/wiki/Closure_problem and I have a few questions.
First, at the very beginning, the article says that "a closure of a directed graph is a set of vertices C, such that no edges leave C". So let's say I have a graph G=(V,E) in which V = {a,b,c} and E={(a,b),(b,c),(a,c)}. Then, according to the definition of closure, a closure C(G) = {b,c}, since no edges leaving C.
However, under the Reduction to maximum flow section which is under the Algorithms section, it says that "the set of vertices on the same side of the cut as s automatically forms a closure C" and the figure on the side shows that C={s,1,5,3,2}. However, clearly, there are edges coming out of the closure, such as edge (2,t),(s,7).
So, what are my not understanding correctly here? Thank you!
CodePudding user response：
The vertices s and t are added to the initial graph and the minimal cut found would be closure in an initial graph and not in the modified one. The algorithm heavily relies on the max-flow min-cut theorem. There obviously exists a finite cut as for example, cut with {s} and everything else is finite by construction. Therefore min-cut is also finite, meaning it cannot have any infinite edges, and all edges present in the initial graph are made infinite. Subsequently, the min-cut in the modified graph is also a closure in the initial one.