Editing Maximum flow problem (section)

{{Short description|Computational problem in graph theory}}
{{Use dmy dates|date=May 2022}}
[[File:Pets flow.svg|alt=Flow network for the problem: Each human (r''i'') is willing to adopt a cat (w''i''1) and/or a dog (w''i''2). However each pet (p''i'') has a preference for only a subset of the humans. Find any matching of pets to humans such that the maximum number of pets are adopted by one of its preferred humans.|thumb|252x252px|Flow network for the problem: Each human (r''i'') is willing to adopt a cat (w''i''1) and/or a dog (w''i''2). However each pet (p''i'') has a preference for only a subset of the humans. Find any matching of pets to humans such that the maximum number of pets are adopted by one of its preferred humans.]]
In [[Optimization (mathematics)|optimization theory]], '''maximum flow problems''' involve finding a feasible flow through a [[flow network]] that obtains the maximum possible flow rate.

The maximum flow problem can be seen as a special case of more [[complex network]] flow problems, such as the [[circulation problem]]. The maximum value of an s-t flow (i.e., flow from [[Glossary of graph theory#Direction|source]] s to [[Glossary of graph theory#Direction|sink]] t) is equal to the minimum capacity of an [[Cut (graph theory)|s-t cut]] (i.e., cut severing s from t) in the network, as stated in the [[max-flow min-cut theorem]].