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:
“I’m beginning to think that the proper definition of “Man” is “an animal that writes letters.””
—Lewis Carroll [Charles Lutwidge Dodgson] (1832–1898)
“No man, not even a doctor, ever gives any other definition of what a nurse should be than this—”devoted and obedient.” This definition would do just as well for a porter. It might even do for a horse. It would not do for a policeman.”
—Florence Nightingale (1820–1910)
“Mothers often are too easily intimidated by their children’s negative reactions...When the child cries or is unhappy, the mother reads this as meaning that she is a failure. This is why it is so important for a mother to know...that the process of growing up involves by definition things that her child is not going to like. Her job is not to create a bed of roses, but to help him learn how to pick his way through the thorns.”
—Elaine Heffner (20th century)