Let
a graph $G = (V,E)$
a network $N = (G, s, t, c)$
and an integral flow funtion $f$
The value of f $v(f)=v_1+v_2+...+v_p$, where $v_i$ is a flow leaving the source.
I must prove that there are $p$ integral flows functions so that $v(f_i)=v_i$ and
$f = f_1+f_2+...+f_p$.
So I have to split the initial flow into $p$ flows so that the sum of the new flows is the original flow and $v(fi)=vi$.
I followed those instructions manually on some examples, but I can't find an algorithm to fit on all cases.
Any ideas on how I should do it?
I am not perfectly sure that I correctly interpreted all notions, not defined in the question, but I guess that the following solution is OK.
It suffices to prove the claim when $v_i=1$ for each $i$. This will allow us to split the flow $f$ into $v(f)$ flows with value $1$ each. Then given arbitrary natural $v_i$’s with $\sum v_i=v(f)$, we partition these $v(f)$ onto $p$ groups consisting of $v_1,\dots, v_p$ flows respectively, and next for each $i$ we merge flows of $i$-th group into one flow with value $v_i$.
We prove the possibility of splitting a flow $f$ into $v(f)$ flows of value $1$ by induction with respect to $v(f)>0$. If $v(f)=1$ then we put $f_1=f$. Assume that we have already proved the claim for $v(f)=p$. Let $f$ be any feasible integral $s-t$ flow on $N$ with $v(f)=p+1$ Start from $s$ and go along the flow $f$ (that is, along edges $e$ such that $f(e)>0$), subtracting $1$ from $f$ on each passed edge. Since both the graph $G$ and the number $v(f)$ are finite, we can subtract only finitely many $1$’s, so we shall stick at some step. Since $\operatorname{netinflow}(f, v)= \operatorname{netoutlow} (f, v)$ for all vertices $v$ in $G$ except $s$ and $t$, and $\operatorname{netinflow}(f, s)=0$, we can stick only at the vertex $t$. So we went a path from $s$ to $t$. This path endowed with the values which we subtracted, naturally generate an integral flow $f’$ from $s$ to to $t$ with $v(f’)=1$. Putting $f’’=f-f’$ we obtain a feasible integral $s-t$ flow on $N$ with $v(f’)=p$, which can be split into $p$ required flows by the induction hypothesis.