Question

Suppose that, in addition to edge capacities, a flow network has vertex capacities. That is each vertex has a limit l./ on how much flow can pass though . Show how to transform a flow network G D .V; E/ with vertex capacities into an equivalent flow network G0 D .V 0 ; E0 / without vertex capacities, such that a maximum flow in G0 has the same value as a maximum flow in G. How many vertices and edges does G0 have?

Answer 1

Answer:

See explanation and answer below.

Step-by-step explanation:

The tranformation

For this case we need to construct G' dividing making a division for each vertex v of G into 3 edges that on this case are $v_1, v_2 and l(v)$.

We assume that the edges from the begin are the incoming edges of $v_1$ and all the outgoing edges from v are outgoing edges from $v_2$

We need to construct $G' = (V', E')$ with capacity function a' and we need to satisfy the follwoing:

For every $v \in V$ we create 2 vertices $v_1, v_2 \in V'$

Now we can add a new edge asscoiated to $v_1, v_2 \in E'$ with the condition $a' (v_1,v_2) = l(v)$

Now for each edges $(u,v)\in E$ we can create the following edge $( u_r, v_1) \in E'$ and the capacity is given by: $a' (u_r, v_1) = a (u,v)$

And for this case we can see this:

$|V'| = 2|V|, |E'|= |E| +|V|$

Now we assume that x is the flow who belongs to G respect vertex capabilities. We can create a flow function x' who belongs to G' with the following steps:

For every edge $(u,v) \in G$ we can assume that $x' (u_r ,v_1) = x(u,v)$

Then for each vertex $u \in V -t$ and we can define $x\(u_1,u_r) = \sum_{v \in V} x(u,v)$ and $x' (t_1,t_2) = \sum_{v \in V} x(v,t)$

And after see that the capacity constraint on this case would be satisfied since for every edge in G' on the form $(u_r, u_1)$ we have a corresponding edge in G because:

$u \in V -(s,t)$ we have that:

$x' (u_1, u_r) = \sum_{v \in V} x(u,v) \leq l(u) = a' (u_1, u_r)$

$x' (t_1,t_2) = \sum_{v \in V} x(v,t) \leq (t) = a' (t_1,t_2)$

And with this we have the maximization problem solved.  

We assume that we have K vertices using the max scale algorithm.