|
In graph theory, a network flow is an assignment of flow to the edges of a directed graph (called a flow network in this case) where each edge has a capacity, such that the amount of flow along an edge does not exceed its capacity. In addition you have the restriction that the amount of flow into a node equals the amount of flow out of it, except if it is a source, which only has outgoing flow, or sink, which has only incoming flow. A flow network can be used to simulate traffic in a road system, fluids in pipes, currents in an electrical circuit, or anything similar in which something travels through a network of nodes.
Definition Given a graph with nodes and edges , and special nodes source (in-degree 0) and sink (out-degree 0). Let be the flow from node to node , and the capacity (maximum flow possible). A network flow is a real function with the following three properties for all nodes and : 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 an edge from to in the residual network, even though there is no edge 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 , where , , and , which means it is possible to send more flow along this path. Example
Applications Picture a series of channels,fitting into a network. Each channel 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 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. Generalisations and specialisations The simplest and most common problem using network flow is to find what is called the maximum flow, which provides the largest possible total flow from the source to the sink in a given graph. There are many other problems which can be solved using max flow algorithms, if they are appropriately modeled as flow networks, such as bipartite matching, assignment problem, transportation problem. In a multi-commodity flow problem, you have multiple sources and sinks, and various "commodities" which are to flow from a given source to a given sink. This could be for example various goods that are produced at various factories, and are to be delivered to various given customers through the same transportation network. In a minimum cost flow problem, each edge has a given cost , and the cost of sending the flow across the edge is . The object is to send a given amount of flow from the source to the sink, at the lowest possible price. In a circulation problem, you have a lower bound on the edges, in addition to the upper bound . Each edge also has a cost. Often, flow conservation holds for all nodes in a circulation problem, and there is a connection from the sink back to the source. In this way, you can dictate the total flow with and . The flow circulates through the network, hence the name of the problem. See also | ||||||||||
|
| |||||||||||
![]() |
|
| |