2
$\begingroup$

Need help with this question from my Intro to Algorithms book:

Show that splitting an edge in a flow network yields an equivalent network. More formally, suppose that flow network $G$ contains edge $(u,v)$, and we create a new flow network $G'$ by creating a new vertex $x$ and replacing $(u,v)$ by new edges $(u,x)$ and $(x,v)$ with $c(u,x) = c(u,v)$. Show that a maximum flow in $G'$ has the same value as a maximum flow in $G$.

$\endgroup$
0
$\begingroup$

we split the edge (u,v) such that there is an edge (u,x) and (x,y) and the flow is the same across the new edge,i.e c(u,x)=c(x,y) =c(u,v).

So instead of a single edge etween u and v there is a 2 edge ut the overall flow is the same.So when we consider the flow network, nothing has chandged.The flow from u to v will remain the same as in the original graph except that now it flows from u to v through x.

$\endgroup$
0
$\begingroup$

We need to show each flow in $G$ corresponds to a flow in $G'$ and vice versa.

One direction: Suppose we have some flow in $G$. Since we are only changing one of the edges of an anti-parallel edge-pair, we have an identical flow through all other edges(unchanged edges). Let $f(u,v)$ is the flow along edge $(u,v)$ in $G$. Also note that the capacity of both of the two new edges are same, we can set $f'(u, v) = f '(u, x) = f'(x, v)$. Now it is easy to see that this flow is identical to the original one and we also have a valid flow.

Other direction: It is very easy. Here $f_{in}(x) = f_{out}(x)$ and there is only one incoming and only one outgoing edge. So, we can remove the vertex $x$ and replace the edges $(u,x)$ and $(x,v)$ with edge $(u,v)$ with flow $f'(u,v)=f'(u,x)=f'(x,v)$.

So, each flow in $G$ corresponds to a flow in $G'$ and each flow in $G'$ corresponds to a flow in $G$.

$\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.