Definition
Let be a network (directed graph) with and being the source and the sink of respectively.
- The capacity of an edge is a mapping c: E→R+, denoted by cuv or c(u,v). It represents the maximum amount of flow that can pass through an edge.
- A flow is a mapping f: E→R+, denoted by fuv or f(u,v), subject to the following two constraints:
- for each (capacity constraint)
- for each (conservation of flows).
- 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.
Read more about this topic: Max-flow Min-cut Theorem
Famous quotes containing the word definition:
“Although there is no universal agreement as to a definition of life, its biological manifestations are generally considered to be organization, metabolism, growth, irritability, adaptation, and reproduction.”
—The Columbia Encyclopedia, Fifth Edition, the first sentence of the article on “life” (based on wording in the First Edition, 1935)
“The physicians say, they are not materialists; but they are:MSpirit is matter reduced to an extreme thinness: O so thin!—But the definition of spiritual should be, that which is its own evidence. What notions do they attach to love! what to religion! One would not willingly pronounce these words in their hearing, and give them the occasion to profane them.”
—Ralph Waldo Emerson (1803–1882)
“Perhaps the best definition of progress would be the continuing efforts of men and women to narrow the gap between the convenience of the powers that be and the unwritten charter.”
—Nadine Gordimer (b. 1923)