![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/2/2f/Pets_flow.svg/640px-Pets_flow.svg.png&w=640&q=50)
Maximum flow problem
Computational problem in graph theory / From Wikipedia, the free encyclopedia
In optimization theory, maximum flow problems involve finding a feasible flow through a flow network that obtains the maximum possible flow rate.
![Flow network for the problem: Each human (ri) is willing to adopt a cat (wi1) and/or a dog (wi2). However each pet (pi) 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.](http://upload.wikimedia.org/wikipedia/commons/thumb/2/2f/Pets_flow.svg/320px-Pets_flow.svg.png)
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 source s to sink t) is equal to the minimum capacity of an s-t cut (i.e., cut severing s from t) in the network, as stated in the max-flow min-cut theorem.