Max-flow Min-cut Theorem - Definition

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:
  1. for each (capacity constraint)
  2. 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:

    “It is very hard to give a just definition of love. The most we can say of it is this: that in the soul, it is a desire to rule; in the spirit, it is a sympathy; and in the body, it is but a hidden and subtle desire to possess—after many mysteries—what one loves.”
    —François, Duc De La Rochefoucauld (1613–1680)

    “According to our social pyramid, all men who feel displaced racially, culturally, and/or because of economic hardships will turn on those whom they feel they can order and humiliate, usually women, children, and animals—just as they have been ordered and humiliated by those privileged few who are in power. However, this definition does not explain why there are privileged men who behave this way toward women.”
    —Ana Castillo (b. 1953)