Lagmental Vicfred

Max-Flow Equals Min-Cut by Vicfred

tags: mathematics, paths, network flows, matchings

The largest feasible source-to-sink flow has value equal to the smallest cut capacity. The example is deliberately concrete; it is a test of the statement, not a substitute for it.

Definitions first

Weighted paths minimize \(\sum_{e\in P}w(e)\), flows use values \(f:E\to\mathbf R_{\ge0}\) with conservation, and matchings enforce degree at most one. Each problem has a dual obstruction.

$$ 0\le f(e)\le c(e),\qquad\sum_{e\in\delta^-(v)}f(e)=\sum_{e\in\delta^+(v)}f(e) $$

I keep the defining relation \(\mathsf D\) above the derived relation \(\mathsf C\). This exposes whether cancellation used \(x\ne0\) and whether the conclusion is canonical.

$$ \max_f|f|=\min_{S\ni s,\ t\notin S}c(S,V\setminus S) $$

A small case in full

Now evaluate one representative case. The result should agree with the structural law above, but it is obtained without assuming the conclusion.

$$ |f|=\sum_{u\in S,v\notin S}f(u,v)-\sum_{u\notin S,v\in S}f(u,v)\le\sum_{u\in S,v\notin S}c(u,v) $$

The reusable statement

The aligned summary deliberately puts the datum and conclusion on different rows. Mathematically, this is the distinction between specifying an object and proving a property of it.

$$ \begin{aligned} \mathsf{D}\;&:\quad 0\le f(e)\le c(e),\qquad\sum_{e\in\delta^-(v)}f(e)=\sum_{e\in\delta^+(v)}f(e),\\[5pt] \mathsf{C}\;&:\quad \max_f|f|=\min_{S\ni s,\ t\notin S}c(S,V\setminus S). \end{aligned} $$

A nearby false statement

Dijkstra requires nonnegative edge weights, while flow capacities must be interpreted on a directed residual network even when the original graph is undirected.

$$ \boxed{\begin{gathered} \text{compact conclusion}\\[-2pt] \max_f|f|=\min_{S\ni s,\ t\notin S}c(S,V\setminus S) \end{gathered}} $$

This is enough machinery for one note: an exact object, a worked case, a structural law, and a clearly marked boundary. Each layer can now be tested independently.

This article was posted on Fri 26 March 2010. Facts and circumstances may have changed since publication.
Please contact me before jumping to conclusions if something seems wrong or unclear.