flow+flow is a flow

48 Views Asked by At

I have the following question: If $f$ is an $s$-$t$ flow in $(G,\mu, s, t)$ and $f'$ is an $s$-$t$ flow in $(G,\mu', s, t)$ then there exists an $s$-$t$ flow in $(G, \mu +\mu', s, t)$ of value $|f|+|f'|$. ($\mu$ and $\mu'$ are the capacities)

Intuitively I would say this is correct, right?

1

There are 1 best solutions below

3
On BEST ANSWER

Yes, it is true. To prove it, write down the linear constraints satisfied by $f$ and $f'$ and show that $f+f'$ satisfies the linear constraints that define an $s$-$t$ flow with the new capacities.