Network flow
|
|
In graph theory, a network flow is an assignment of values to edges of a weighted directed graph (called a flow network in this case), such that:
1. The value along an edge never exceeds the weight of that edge (here known as the capacity).
2. The total incoming flow of some node (i.e. the sum of the values of all edges coming into the node) exactly equal the total outgoing flow, with the exception of two special nodes s and t. The node s can have any outgoing flow but no incoming flow, while the node t can have any incoming flow, and no outgoing flow.
In such a situation, s is considered a source and t is considered a sink.
This is a technical description. It is easier to think of flows in terms of physical systems. Imagine a bunch of pipes, fitting into a network. Each pipe is of a certain width, so it can only maintain a flow of a certain amount of water. Anywhere that pipes meet, the total amount of water coming into that junction must be equal to the amount going out, otherwise we would quickly run out of water, or we would have a build up of water. We have a water inlet, which is the source, and an outlet, the sink. A flow would then be one possible way for water to get from source to sink so that the total amount of water coming out of the outlet is consistent. Intuitively, the total flow of a network flow is the rate at which water comes out of the outlet.
Flows can pertain to people or material over transportation networks, or to electricity over electrical distribution systems. For any such physical network, the flow coming into any intermediate node needs to equal the flow going out of that node. Bollobás characterizes this constraint in terms of Kirchhoff's current law, while later authors (ie: Chartrand) mention its generalization to some conservation equation.
A common problem is to find what is called the max flow, which provides the largest total flow value for the given graph. There are several algorithms which have been discovered to solve this. The most famous of these are the Ford-Fulkerson algorithm and the Relabel-to-front algorithm.
There are many problems which can be solved using max flow algorithms, if they are appropriately modeled as flow networks, such as bipartite matching