Editing Flow network (section)

==Concepts useful to flow problems==

=== Flow decomposition ===
Flow decomposition<ref>{{Cite book |last=Ahuja |first=Ravindra K. |title=Network flows: theory, algorithms and applications |last2=Magnanti |first2=Thomas L. |last3=Orlin |first3=James B. |date=1993 |publisher=Prentice Hall |isbn=978-0-13-617549-0 |location=Englewood Cliffs (N. J.)}}</ref> 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|date=June 2023}}
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:
*Given any two nodes {{mvar|u}} and {{mvar|v}}, having two arcs from {{mvar|u}} to {{mvar|v}} with capacities {{math|''c''<sub>1</sub>(''u,v'')}} and {{math|''c''<sub>2</sub>(''u,v'')}} respectively is equivalent to considering only a single arc from {{mvar|u}} to {{mvar|v}} with a capacity equal to {{math|''c''<sub>1</sub>(''u,v'')+''c''<sub>2</sub>(''u,v'')}}.
*Given any two nodes {{mvar|u}} and {{mvar|v}}, having two arcs from {{mvar|u}} to {{mvar|v}} with pseudo-flows {{math|''f''<sub>1</sub>(''u,v'')}} and {{mvar|''f''<sub>2</sub>(''u,v'')}} respectively is equivalent to considering only a single arc from {{mvar|u}} to {{mvar|v}} with a pseudo-flow equal to {{math|''f''<sub>1</sub>(''u,v'')+''f''<sub>2</sub>(''u,v'')}}.
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|date=February 2023}}

===Residuals===
The '''residual capacity''' of an arc {{mvar|e}} with respect to a pseudo-flow {{mvar|f}} is denoted {{math|''c''<sub>''f''</sub>}}, and it is the difference between the arc's capacity and its flow. That is, {{math|''c''<sub>''f''</sub> (''e'') {{=}} ''c''(''e'') &minus; ''f''(''e'')}}. From this we can construct a '''residual network''', denoted {{math|''G''<sub>''f''</sub> (''V'', ''E''<sub>''f''</sub>)}}, with a capacity function {{math|''c''<sub>''f''</sub>}} which models the amount of ''available'' capacity on the set of arcs in {{math|''G'' {{=}} (''V'', ''E'')}}. More specifically, capacity function {{math|''c''<sub>''f''</sub>}} of each arc {{math|(''u'', ''v'')}} in the residual network represents the amount of flow which can be transferred from {{mvar|u}} to {{mvar|v}} 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|u}} to {{mvar|v}} in the residual network, even though there is no such path from {{mvar|u}} to {{mvar|v}} in the original network.{{Citation needed|date=January 2023}} Since flows in opposite directions cancel out, ''decreasing'' the flow from {{mvar|v}} to {{mvar|u}} is the same as ''increasing'' the flow from {{mvar|u}} to {{mvar|v}}.

===Augmenting paths===
An '''augmenting path''' is a path {{math|(''u''<sub>1</sub>, ''u''<sub>2</sub>, ..., ''u''<sub>''k''</sub>)}} in the residual network, where {{math|''u''<sub>1</sub> {{=}} ''s''}}, {{math|''u''<sub>''k''</sub> {{=}} ''t''}}, and {{math|for all ''u''<sub>''i''</sub>, ''u''<sub>''i'' + 1</sub> (''c''<sub>''f''</sub> (''u''<sub>''i''</sub>, ''u''<sub>''i'' + 1</sub>) > 0) (1 ≤ i < k)}}. 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|''G''<sub>''f''</sub>}}.

The '''bottleneck''' is the minimum residual capacity of all the edges in a given augmenting path.<ref name=":0">{{Cite book |last=Kleinberg |first=Jon |url=https://www.worldcat.org/oclc/796210667 |title=Algorithm design |date=2011 |publisher=Addison-Wesley |others=Éva Tardos |isbn=978-0-13-213108-7 |edition=2nd |location=Boston, Mass. |pages=342, 346 |oclc=796210667}}</ref> 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|f}} of each arc in this augmenting path to equal the capacity {{math|''c''}} 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.<ref>{{DADS|Supersource|supersource}}</ref> 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'''.<ref>{{DADS|Supersink|supersink}}</ref>