Analysis of Max flow min cut theorem and its generalization

  Monika Yadav

The value of flow is defined by, where is the source of . It represents the amount of flow passing from the source to the sink. The maximum flow problem is to maximize | f |, that is, to route as much flow as possible from s to t. An s-t cut C = (S,T) is a partition of V such that s∈S and t∈T. The cut-set of C is the set {(u,v)∈E | u∈S, v∈T}. Note that if the edges in the cut-set of C are removed, | f | = 0. The capacity of an s-t cut is defined by The minimum s-t cut problem is minimizing, that is, to determine S and T such that the capacity of the S-T cut is minimal. In other words, the amount of flow passing through a vertex cannot exceed its capacity. Define an s-t cut to be the set of vertices and edges such that for any path from s to t, the path contains a member of the cut. In this case, the capacity of the cut is the sum the capacity of each edge and vertex in it. In this new definition, the generalized max-flow min-cut theorem states that the maximum value of an s-t flow is equal to the minimum capacity of an s-t cut in the new sense.

Keywords- minimizing, partition, vertex, theorem, max-flow

Unique Identification Number - IJEDR1704079
Page Number(s) - 508-511
Pubished in - Volume 5 | Issue 4 | November 2017
DOI (Digital Object Identifier) -   
Publisher - IJEDR (ISSN - 2321-9939)

  Monika Yadav,   "Analysis of Max flow min cut theorem and its generalization", International Journal of Engineering Development and Research (IJEDR), ISSN:2321-9939, Volume.5, Issue 4, pp.508-511, November 2017, Available at :http://www.ijedr.org/papers/IJEDR1704079.pdf