Max-flow-min-cut Theorem explanation behind proof

427 Views Asked by At

The theorem states the following:

In any network $(G, s, t, c)$ $(G$ is a directed graph, $s$ is the source, $t$ is the sink, $c$ are the capacities $)$ we have $\sup\{ v(f) : f$ is a feasible flow $\} = \min \{ c(S, T) : (S, T)$ is a cut }$

Moreover, the supremum is attained

The proof in the lecture notes is attached

enter image description here

The problem starts at "Repeating this for each edge, we find a subsequence of flows with $v(f_i) \rightarrow M$ such that $f_i(x,y)$ converges for each... "

If we choose $1$ edge, we can find this convergent subsequence, for example by finding a monotone sequence and using standard analysis results. But when we choose the second edge, how do we guarantee that the sequence of flows converges for both of the edges?

Thanks in advance

1

There are 1 best solutions below

1
On BEST ANSWER

The trick is a standard analysis one:

Let $f_n(x_1y_1)$ and $f_n(x_2y_2)$ be two sequences. We can then find a subsequence $f_{k_n}(x_1y_1)$ which is convergent. Next, instead of looking at $f_n(x_2y_2)$, look at the subsequence $f_{k_n}(x_2y_2)$. This is bounded, thus it has a converegent subsequence $f_{l_n}(x_2y_2)$.

Now, since $f_{l_n}(x_1y_1)$ is a subsequence of $f_{k_n}(x_1y_1)$ it is convergent.

Note This is actually an argument about compatcness. In $\mathbb R^d$ a set is compact if it is closed and bounded. Thus by boundedness, the sequence $$(f_n(x_1y_1), f_n(x_2y_2),..., f_n(x_dy_d)$$ has a convergent subsequence in some closed ball in $\mathbb R^d$.