Network flow stems from our original Bipartite Matching problem. This problem can model situations where objects need to be matched and when we need collections of pairs. We could also look for the largest matching set.

A flow network is a graph where each edge has an non-negative capacity associated with it. The is one source node and one sink node and these follow the standard definitions. Flow must not be greater than the capacity of the edge it travels on and it must also be conserved, that is, flow into a node must equal the flow out of a node (except for the source and sink nodes). The total value of the flow is the amount of flow out of the source node.

The Maximum-Flow problem asks us to find the greatest value of flow possible for a network such that the capacity and conservation are not violated. We say that the maximum flow from one set A into another set B must equal the minimum capacity of all edges that divide A and B. Because a natural greedy algorithm does not work, we need to find a new solution. We define a residual graph as the same sets of nodes as in the original graph, but with each edge's capacity decreased to that of the remaining capacity and reversed edge of the flow through the original edge. We check our residual graph for an augmenting path to see if we can add flow. We can run the Ford-Fulkerson algorithm on this problem in O(m+n) time.