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:
“I’m beginning to think that the proper definition of “Man” is “an animal that writes letters.””
—Lewis Carroll [Charles Lutwidge Dodgson] (1832–1898)
“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 man who knows governments most completely is he who troubles himself least about a definition which shall give their essence. Enjoying an intimate acquaintance with all their particularities in turn, he would naturally regard an abstract conception in which these were unified as a thing more misleading than enlightening.”
—William James (1842–1910)