1
$\begingroup$

I am given a homework assignment on this question:

Show that if we add any number of incoming arcs, with any capacities, to the source node, the maximum flow value remains unchanged. Similarly, show that if we add any number of outgoing arcs, with any capacities, at the sink node, the maximum flow value remains unchanged.

While, it can be graphically proved with the help of an example, I am unsure of how to prove it systematically (like usual proofs in textbooks)

|cite|improve this question
$\endgroup$
  • $\begingroup$ Instead of directly proving it, have you tried reductio ad absurdum? Try assuming that adding an incoming arc at the source node changes the maximum flow, and proceed applying definitions. At some point you'll likely contradict a hypothesis and therefore proving your original point. $\endgroup$ – Emanuele Giona Nov 9 '18 at 13:36
1
$\begingroup$

Let $G=(V,E)$ be your input graph. Now consider a maximum flow $f$ on $G$.

Let $f$ be a flow in $G$ such that the residual network $G_R$ has no s-t path, then $f$ is a maximum flow.

Let's define $G'=(V,E')$ to be your graph with $E'=E \cup \{(u_i,s)\}$ for $i=1,...,N$.

Since $f$ is a maximum flow on $G$, then $G_R$ has no s-t paths.
Now you can show that given $G'$, its residual network $G'_R$ does not have any s-t path too. Thus, $f$ is a max flow also for $G'$.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Good, but why $c(u_i, s) $ must be 0. It has no effect on your solution. Moreover, it's part of the problem's requirements that it can have any capacity. $\endgroup$ – Ahmad Nov 9 '18 at 10:38
  • $\begingroup$ You're right, it was my misread. $\endgroup$ – abc Nov 9 '18 at 13:41
0
$\begingroup$

One way would be to show that, in any network, there is a maximum flow which has no flow coming into the source $s$. There are a couple more hints below; don't look at them unlessy ou need to.

Hint about how to do this:

If is flow into $s$, there must be some cycle $sv_1\dots v_ks$ with positive flow around it. You can decrease the flow around that cycle to zero without affecting the total flow into the sink $t$.

Hint about why this is useful:

It shows that adding edges into the source doesn't increase the network's capacity.

Essentially the same argument deals with out-edges from the sink.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.