The MaxFlow command solves the s to t maximum flow problem using edge weights of G as the flow capacities between vertices. If G is not a weighted graph then every edge is taken to have a capacity of 1. If G is a multigraph every edge is taken to have a capacity equal to its multiplicity. An undirected Graph is treated as a directed graph with edges in both directions, but the output flow matrix will be directional.

This command returns two things: the optimal value for the maximum flow from the vertex s to the vertex t and a sparse matrix of the flows at each edge which achieve that optimal flow. The maximum flow value is unique, while the flow matrix may be one of several possible flows that achieve that maximum.

MaxFlow uses the Push-Relabel (Push-Preflow) algorithm of Goldberg et al. (see Introduction to Algorithms, Cormen, Leiserson, Rivest, 2nd edition). The complexity is $\mathrm{O}\left(n^{2}m\right)$ where $n$ is the number of vertices of G and $m$ is the number of edges.

$\mathrm{with}\left(\mathrm{GraphTheory}\right)\:$

$A≔\mathrm{Matrix}\left(\left[\left[0\,1\,0\,4\,0\,0\right]\,\left[0\,0\,2\,0\,3\,0\right]\,\left[0\,1\,0\,0\,0\,1\right]\,\left[0\,0\,3\,0\,1\,0\right]\,\left[0\,0\,0\,2\,0\,4\right]\,\left[0\,0\,0\,0\,0\,0\right]\right]\right)$

$A≔\left[\begin{array}{cccccc}0& 1& 0& 4& 0& 0\\ 0& 0& 2& 0& 3& 0\\ 0& 1& 0& 0& 0& 1\\ 0& 0& 3& 0& 1& 0\\ 0& 0& 0& 2& 0& 4\\ 0& 0& 0& 0& 0& 0\end{array}\right]$

$N≔\mathrm{Graph}\left(A\,'\mathrm{weighted}'\right)$

$N≔\mathrm{Graph\; 1:\; a\; directed\; weighted\; graph\; with\; 6\; vertices\; and\; 10\; arc(s)}$

$\mathrm{IsNetwork}\left(N\right)$

$\left\{1\right\},\left\{6\right\}$

$\mathrm{DrawNetwork}\left(N\right)$

$\mathrm{mf},F≔\mathrm{MaxFlow}\left(N\,1\,6\right)$

$\mathrm{mf},F≔4,\left[\begin{array}{cccccc}0& 1& 0& 3& 0& 0\\ 0& 0& 0& 0& 2& 0\\ 0& 1& 0& 0& 0& 1\\ 0& 0& 2& 0& 1& 0\\ 0& 0& 0& 0& 0& 3\\ 0& 0& 0& 0& 0& 0\end{array}\right]$

$M≔\mathrm{Graph}\left(F\,'\mathrm{weighted}'\right)$

$M≔\mathrm{Graph\; 2:\; a\; directed\; weighted\; graph\; with\; 6\; vertices\; and\; 8\; arc(s)}$

$\mathrm{StyleEdgesByProperty}\left(M\,F\,\mathrm{colorscheme}=\left[''Blue''\,''Purple''\,''Red''\right]\,\mathrm{thicknessscheme}=\left[1\,3\right]\right)$

$\mathrm{DrawGraph}\left(M\,'\mathrm{layout}'='\mathrm{network}'\right)$

$\mathrm{G6}≔\mathrm{Graph}\left(\left\{\left\{1\,2\right\}\,\left\{1\,6\right\}\,\left\{2\,3\right\}\,\left\{2\,4\right\}\,\left\{3\,4\right\}\,\left\{3\,5\right\}\,\left\{4\,5\right\}\,\left\{5\,6\right\}\right\}\right)$

$\mathrm{G6}≔\mathrm{Graph\; 3:\; an\; undirected\; graph\; with\; 6\; vertices\; and\; 8\; edge(s)}$

$\mathrm{DrawGraph}\left(\mathrm{G6}\right)$

$\mathrm{mf2},\mathrm{F2}≔\mathrm{MaxFlow}\left(\mathrm{G6}\,1\,6\right)$

$\mathrm{mf2},\mathrm{F2}≔2,\left[\begin{array}{cccccc}0& 1& 0& 0& 0& 1\\ 0& 0& 1& 0& 0& 0\\ 0& 0& 0& 1& 0& 0\\ 0& 0& 0& 0& 1& 0\\ 0& 0& 0& 0& 0& 1\\ 0& 0& 0& 0& 0& 0\end{array}\right]$

$\mathrm{M2}≔\mathrm{Graph}\left(\mathrm{F2}\,'\mathrm{weighted}'\right)$

$\mathrm{M2}≔\mathrm{Graph\; 4:\; a\; directed\; weighted\; graph\; with\; 6\; vertices\; and\; 6\; arc(s)}$

$\mathrm{DrawGraph}\left(\mathrm{M2}\,'\mathrm{layout}'='\mathrm{circle}'\right)$

Cormen, Thomas H., Leiserson, Charles E., Rivest, Ronald L., and Stein, Clifford. Introduction to Algorithms, 2nd edition. Cambridge, Mass., MIT Press, 2001.

The GraphTheory[MaxFlow] command was updated in Maple 2024.