# Maximum Flow Problem **An optimisation problem involved with finding the maximum flow through a [[flow network]].** ![[MaximumFlowNetwork.svg|650]] *A flow network with maximum flow* There are typically *several* maximum flows possible in a flow network. If the capacities and flows were *arbitrarily real* then there is either *exactly one* or *infinitely many* maximum flows possible. ## Theorems ### Integral flow theorem > [!Example] Integral Flow Theorem > If all capacities of a flow network are *integers*, then there exists a *maximum flow* such that $f(v,w)\in\mathbb{Z}$ for each edge $(v,w)\in E$. ### Max-flow min-cut theorem > [!Example] Max-Flow Min-Cut Theorem > The *max-flow min-cut theorem* states that the [[Flow Network#Maximum flow problem|maximum flow]] of a flow network is equal to the capacity of the [[Cut#S-T cut|cut]] of [[Cut#^347522|minimal capacity]]. > > > [!Example]- > > ![[MaxFlowMinCutExample.svg|500]] > > *The network has a maximum flow of 24, which is equal to a cut of minimal capacity* ## Algorithms The first algorithm designed to solve the maximum flow problem is the [[Ford-Fulkerson algorithm]], though it does not specify the method by which [[Flow Network#Augmenting path|augmenting paths]] are found. The most common implementation of the Ford-Fulkerson algorithm is the [[Edmonds-Karp algorithm]]. ## Applications The maximum flow problem can be used to solve other problems provided that their constraints can be modelled by the properties of a flow network and a solution the problem can be modelled as a flow in the network. ### Supply allocation A problem involving a supply of different objects to be distributed can be modelled as a maximum flow problem. Typically, supply and consumers are modelled as two sets of vertices, together with either the source or the sink, as though in a [[bipartite graph]]. The capacity of the edges from the vertices of each set to the source or sink then represent either the supply of an object available or restrictions on the amount of supply a consumer can receive. > [!NOTE]- Example > #unfinished