Trasitivity of maximum flow

41 Views Asked by At

$G=(V,E)$ is a directed graph, $C(e)>0$ for all edges. Is the following correct?

For every $3$ vertices, $u,v,w$, if the max flow from $u$ to $w$ is more than $1000$ and the max flow from $w$ to $v$ is more than $1000$, so the max flow from $u$ to $v$ is more than $1000$.

I assume this is correct. If the two first max flows don't share edges the union of them is a the required max flow from $u$ to $v$. I don't manage to prove it for the general case.

Thanks!

1

There are 1 best solutions below

0
On BEST ANSWER

The max-flow min-cut theorem is probably the easiest way to conceptually tackle this problem. We know that the max flow from $u$ to $w$ is equal to the min cut; now, to make $w$ unreachable from $u$, it is necessary to either make $w$ unreachable from $v$ or $v$ unreachable from $u$; thus, any $u$-$w$ min cut must contain a $u$-$v$ cut or a $v$-$w$ cut, and hence must be at least as large as their respective min cuts, which immediately proves the result.

Alternatively one might think of a proof that notices that you can directly add the $u$-$v$ and $v$-$w$ max flows to yield a result, except when they both have positive flow through the same edge; and then let that edge be $(x, y)$, and modify the $y$-$v$ flow and $v$-$x$ flow to prevent this edge from going over capacity. I haven't thought much about how to make this line of argument rigorous, but feel free to attempt to.