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:
“The definition of good prose is proper words in their proper places; of good verse, the most proper words in their proper places. The propriety is in either case relative. The words in prose ought to express the intended meaning, and no more; if they attract attention to themselves, it is, in general, a fault.”
—Samuel Taylor Coleridge (1772–1834)
“The very definition of the real becomes: that of which it is possible to give an equivalent reproduction.... The real is not only what can be reproduced, but that which is always already reproduced. The hyperreal.”
—Jean Baudrillard (b. 1929)
“I’m beginning to think that the proper definition of “Man” is “an animal that writes letters.””
—Lewis Carroll [Charles Lutwidge Dodgson] (1832–1898)