Definition
is a finite directed graph in which every edge has a non-negative, real-valued capacity . If, we assume that . We distinguish two vertices: a source and a sink . A flow network is a real function with the following three properties for all nodes and :
-
Capacity constraints: . The flow along an edge cannot exceed its capacity. Skew symmetry: . The net flow from to must be the opposite of the net flow from to (see example). Flow conservation: , unless or . The net flow to a node is zero, except for the source, which "produces" flow, and the sink, which "consumes" flow.
Notice that is the net flow from to . If the graph represents a physical network, and if there is a real flow of, for example, 4 units from to, and a real flow of 3 units from to, we have and .
The residual capacity of an edge is . This defines a residual network denoted, giving the amount of available capacity. See that there can be a path from to in the residual network, even though there is no path from to in the original network. Since flows in opposite directions cancel out, decreasing the flow from to is the same as increasing the flow from to . An augmenting path is a path in the residual network, where, and . A network is at maximum flow if and only if there is no augmenting path in the residual network.
Should one need to model a network with more than one source, a supersource is introduced to the graph. This consists of a vertex connected to each of the sources with edges of infinite capacity, so as to act as a global source. A similar construct for sinks is called a supersink.
Read more about this topic: Flow Network
Famous quotes containing the word definition:
“One definition of man is “an intelligence served by organs.””
—Ralph Waldo Emerson (1803–1882)
“Beauty, like all other qualities presented to human experience, is relative; and the definition of it becomes unmeaning and useless in proportion to its abstractness. To define beauty not in the most abstract, but in the most concrete terms possible, not to find a universal formula for it, but the formula which expresses most adequately this or that special manifestation of it, is the aim of the true student of aesthetics.”
—Walter Pater (1839–1894)
“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)