A network flow assigns nonnegative flow values to the graph edges of a directed graph, with total inflow
equal to total outflow at each graph vertex other
than the sources and sinks.
The network flow problem considers a graph with a set of sources and sinks and for which each graph edge
has an assigned capacity (weight), and then asks to
find the maximum flow that can be routed from to
while respecting the given edge capacities. The network
flow problem can be solved in time (Edmonds and Karp 1972; Skiena 1990, p. 237). It
is implemented in the Wolfram Language
as FindMaximumFlow[g,
source, sink].
Brunner, R. and Hanusa, C. R. H. "A Triangulation of the Flow Polytope of the Zigzag Graph." Elec. J. Combin.33,
P4.10, 2026. https://doi.org/10.37236/13162.Edmonds,
J. and Karp, R. M. "Theoretical Improvements in Algorithmic Efficiency
for Network Flow Problems." J. ACM19, 248-264, 1972.Even,
S. and Tarjan, R. E. "Network Flow and Testing Graph Connectivity."
SIAM J. Comput.4, 507-518, 1975.Ford, L. R. and
Fulkerson, D. R. Flows
in Networks. Princeton, NJ: Princeton University Press, 1962.Gonery,
R. E. and Hu, T. C. "Multiterminal Network Flows." J. SIAM9,
551-570, 1961.Orlin, J. B. "A Faster Strongly Polynomial Minimum
Cost Flow Algorithm." Proc. 20th ACM Symposium Theorem of Computing.
pp. 377-387, 1988.Skiena, S. "Network Flow." §6.3
in Implementing
Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading,
MA: Addison-Wesley, pp. 237-239, 1990.Skiena, S. S. "Network
Flow." §8.4.9 in The
Algorithm Design Manual. New York: Springer-Verlag, pp. 297-300, 1997.Tarjan,
R. E. Data
Structures and Network Algorithms. Philadelphia, PA: SIAM, 1983.
with a set of sources 
and sinks 
and for which each graph edge
has an assigned capacity (weight), and then asks to
find the maximum flow that can be routed from 
to 
while respecting the given edge capacities. The network
flow problem can be solved in time 
(Edmonds and Karp 1972; Skiena 1990, p. 237). It
is implemented in the Wolfram Language
as FindMaximumFlow[g,
source, sink].
