Английская Википедия:Flow network

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Шаблон:Short description In graph theory, a flow network (also known as a transportation network) is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge. Often in operations research, a directed graph is called a network, the vertices are called nodes and the edges are called arcs. A flow must satisfy the restriction that the amount of flow into a node equals the amount of flow out of it, unless it is a source, which has only outgoing flow, or sink, which has only incoming flow. A network can be used to model traffic in a computer network, circulation with demands, fluids in pipes, currents in an electrical circuit, or anything similar in which something travels through a network of nodes.

Файл:Network Flow SVG.svg
Sample Figure: A flow network showing flow and capacity

Definition

A network is a directed graph Шаблон:Math with a non-negative capacity function Шаблон:Math for each edge, and without multiple arcs (i.e. edges with the same source and target nodes). Without loss of generality, we may assume that if Шаблон:Math, then Шаблон:Math is also a member of Шаблон:Mvar. Additionally, if Шаблон:Math then we may add Шаблон:Math to E and then set the Шаблон:Math.

If two nodes in Шаблон:Mvar are distinguished – one as the source Шаблон:Mvar and the other as the sink Шаблон:Mvar – then Шаблон:Math is called a flow network.[1]

Flows

Flow functions model the net flow of units between pairs of nodes, and are useful when asking questions such as what is the maximum number of units that can be transferred from the source node s to the sink node t? The amount of flow between two nodes is used to represent the net amount of units being transferred from one node to the other.

The excess function Шаблон:Math represents the net flow entering a given node Шаблон:Mvar (i.e. the sum of the flows entering Шаблон:Mvar) and is defined by<math display="block">x_f(u)=\sum_{w \in V} f(w,u).</math>A node Шаблон:Mvar is said to be active if Шаблон:Math (i.e. the node Шаблон:Mvar consumes flow), deficient if Шаблон:Math (i.e. the node Шаблон:Mvar produces flow), or conserving if Шаблон:Math. In flow networks, the source Шаблон:Mvar is deficient, and the sink Шаблон:Mvar is active.

Pseudo-flows, feasible flows, and pre-flows are all examples of flow functions.

A pseudo-flow is a function Шаблон:Math of each edge in the network that satisfies the following two constraints for all nodes Шаблон:Mvar and Шаблон:Mvar:
A pre-flow is a pseudo-flow that, for all Шаблон:Math}, satisfies the additional constraint:
A feasible flow, or just a flow, is a pseudo-flow that, for all Шаблон:Math}, satisfies the additional constraint:
  • Flow conservation constraint: The total net flow entering a node Шаблон:Mvar is zero for all nodes in the network except the source <math>s</math> and the sink <math>t</math>, that is: Шаблон:Math for all Шаблон:Math. In other words, for all nodes in the network except the source <math>s</math> and the sink <math>t</math>, the total sum of the incoming flow of a node is equal to its outgoing flow (i.e. <math>\sum_{(u,v) \in E} f(u,v) = \sum_{(v,z) \in E} f(v,z) </math>, for each vertex Шаблон:Math).

The value Шаблон:Math of a feasible flow Шаблон:Mvar for a network, is the net flow into the sink Шаблон:Mvar of the flow network, that is: Шаблон:Math. Note, the flow value in a network is also equal to the total outgoing flow of source Шаблон:Mvar, that is: Шаблон:Math. Also, if we define Шаблон:Math as a set of nodes in Шаблон:Math such that Шаблон:Math and Шаблон:Math, the flow value is equal to the total net flow going out of A (i.e. Шаблон:Math).[2] The flow value in a network is the total amount of flow from Шаблон:Mvar to Шаблон:Mvar.

Concepts useful to flow problems

Flow decomposition

Flow decomposition[3] is a process of breaking down a given flow into a collection of path flows and cycle flows. Every flow through a network can be decomposed into one or more paths and corresponding quantities, such that each edge in the flow equals the sum of all quantities of paths that pass through it. Flow decomposition is a powerful tool in optimization problems to maximize or minimize specific flow parameters.

Adding arcs and flows

Шаблон:Unreferenced section We do not use multiple arcs within a network because we can combine those arcs into a single arc. To combine two arcs into a single arc, we add their capacities and their flow values, and assign those to the new arc:

Along with the other constraints, the skew symmetry constraint must be remembered during this step to maintain the direction of the original pseudo-flow arc. Adding flow to an arc is the same as adding an arc with the capacity of zero.Шаблон:Citation needed

Residuals

The residual capacity of an arc Шаблон:Mvar with respect to a pseudo-flow Шаблон:Mvar is denoted Шаблон:Math, and it is the difference between the arc's capacity and its flow. That is, Шаблон:Math. From this we can construct a residual network, denoted Шаблон:Math, with a capacity function Шаблон:Math which models the amount of available capacity on the set of arcs in Шаблон:Math. More specifically, capacity function Шаблон:Math of each arc Шаблон:Math in the residual network represents the amount of flow which can be transferred from Шаблон:Math to Шаблон:Math given the current state of the flow within the network.

This concept is used in Ford–Fulkerson algorithm which computes the maximum flow in a flow network.

Note that there can be an unsaturated path (a path with available capacity) from Шаблон:Mvar to Шаблон:Mvar in the residual network, even though there is no such path from Шаблон:Mvar to Шаблон:Mvar in the original network.Шаблон:Citation needed Since flows in opposite directions cancel out, decreasing the flow from Шаблон:Mvar to Шаблон:Mvar is the same as increasing the flow from Шаблон:Mvar to Шаблон:Mvar.

Augmenting paths

An augmenting path is a path Шаблон:Math in the residual network, where Шаблон:Math, Шаблон:Math, and Шаблон:Math. More simply, an augmenting path is an available flow path from the source to the sink. A network is at maximum flow if and only if there is no augmenting path in the residual network Шаблон:Math.

The bottleneck is the minimum residual capacity of all the edges in a given augmenting path.[2] See example explained in the "Example" section of this article. The flow network is at maximum flow if and only if it has a bottleneck with a value equal to zero. If any augmenting path exists, its bottleneck weight will be greater than 0. In other words, if there is a bottleneck value greater than 0, then there is an augmenting path from the source to the sink. However, we know that if there is any augmenting path, then the network is not at maximum flow, which in turn means that, if there is a bottleneck value greater than 0, then the network is not at maximum flow.

The term "augmenting the flow" for an augmenting path means updating the flow Шаблон:Mvar of each arc in this augmenting path to equal the capacity Шаблон:Math of the bottleneck. Augmenting the flow corresponds to pushing additional flow along the augmenting path until there is no remaining available residual capacity in the bottleneck.

Multiple sources and/or sinks

Sometimes, when modeling a network with more than one source, a supersource is introduced to the graph.[4] 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.[5]

Example

Шаблон:Unreferenced section

Файл:Network Flow SVG.svg
Figure 1: A flow network showing flow and capacity
Файл:Network Flow Cropped2 - revised.png
Figure 2: An alternative notation for a flow network showing flow and capacity

In Figure 1 you see a flow network with source labeled Шаблон:Mvar, sink Шаблон:Mvar, and four additional nodes. The flow and capacity is denoted <math>f/c</math>. Notice how the network upholds the skew symmetry constraint, capacity constraint, and flow conservation constraint. The total amount of flow from Шаблон:Mvar to Шаблон:Mvar is 5, which can be easily seen from the fact that the total outgoing flow from Шаблон:Mvar is 5, which is also the incoming flow to Шаблон:Mvar. Note, Figure 1 is often written in the notation style of Figure 2.

Файл:Network flow residual SVG.svg
Figure 3: Residual network for the above flow network, showing residual capacities

In Figure 3 you see the residual network for the given flow. Notice how there is positive residual capacity on some edges where the original capacity is zero in Figure 1, for example for the edge <math>(d,c)</math>. This network is not at maximum flow. There is available capacity along the paths <math>(s,a,c,t)</math>, <math>(s,a,b,d,t)</math> and <math>(s,a,b,d,c,t)</math>, which are then the augmenting paths.

The bottleneck of the <math>(s,a,c,t)</math> path is equal to <math>\min(c(s,a)-f(s,a), c(a,c)-f(a,c), c(c,t)-f(c,t))</math> <math>=\min(c_f(s,a), c_f(a,c), c_f(c,t))</math> <math>= \min(5-3, 3-2, 2-1)</math> <math>= \min(2, 1, 1) = 1</math>.

Applications

Шаблон:See also Шаблон:Unreferenced section

Picture a series of water pipes, fitting into a network. Each pipe is of a certain diameter, 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 buildup 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. This conservation constraint is equivalent to Kirchhoff's current law.

Flow networks also find applications in ecology: flow networks arise naturally when considering the flow of nutrients and energy between different organisms in a food web. The mathematical problems associated with such networks are quite different from those that arise in networks of fluid or traffic flow. The field of ecosystem network analysis, developed by Robert Ulanowicz and others, involves using concepts from information theory and thermodynamics to study the evolution of these networks over time.

Classifying flow problems

The simplest and most common problem using flow networks 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, the assignment problem and the transportation problem. Maximum flow problems can be solved in polynomial time with various algorithms (see table). The max-flow min-cut theorem states that finding a maximal network flow is equivalent to finding a cut of minimum capacity that separates the source and the sink, where a cut is the division of vertices such that the source is in one division and the sink is in another.

Well-known algorithms for the Maximum Flow Problem
Inventor(s) Year Time
complexity
(with Шаблон:Math nodes
and Шаблон:Math arcs)
Dinic's algorithm 1970 Шаблон:Math
Edmonds–Karp algorithm 1972 Шаблон:Math
MPM (Malhotra, Pramodh-Kumar, and Maheshwari)
algorithm[6] 		1978 Шаблон:Math
Push–relabel algorithm (Goldberg & Tarjan) 1988 Шаблон:Math
James B. Orlin[7] 2013 Шаблон:Math
Li Chen, Rasmus Kyng, Yang P. Liu,

Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva

2022 <math>O(m^{1+o(1)})</math>

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 <math>u,v</math> has a given cost <math>k(u,v)</math>, and the cost of sending the flow <math>f(u,v)</math> across the edge is <math>f(u,v) \cdot k(u,v)</math>. The objective 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 <math>\ell(u,v)</math> on the edges, in addition to the upper bound <math>c(u,v)</math>. 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 <math>\ell(t,s)</math> and <math>c(t,s)</math>. The flow circulates through the network, hence the name of the problem.

In a network with gains or generalized network each edge has a gain, a real number (not zero) such that, if the edge has gain g, and an amount x flows into the edge at its tail, then an amount gx flows out at the head.

In a source localization problem, an algorithm tries to identify the most likely source node of information diffusion through a partially observed network. This can be done in linear time for trees and cubic time for arbitrary networks and has applications ranging from tracking mobile phone users to identifying the originating source of disease outbreaks.[8]

See also

References

Шаблон:Reflist

Further reading

External links

Шаблон:Commons

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ A.V. Goldberg, É. Tardos and R.E. Tarjan, Network flow algorithms, Tech. Report STAN-CS-89-1252, Stanford University CS Dept., 1989
  2. ↑ 2,0 2,1 Шаблон:Cite book
  3. ↑ Шаблон:Cite book
  4. ↑ Шаблон:DADS
  5. ↑ Шаблон:DADS
  6. ↑ Шаблон:Cite journal
  7. ↑ Шаблон:Cite book
  8. ↑ Шаблон:Cite journal
Источник — http://wikihandbk.com/ruwiki/index.php?title=Английская_Википедия:Flow_network&oldid=14727764