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?

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 .

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

We need to construct with capacity function a' and we need to satisfy the follwoing:

For every we create 2 vertices

Now we can add a new edge asscoiated to with the condition

Now for each edges we can create the following edge and the capacity is given by:

And for this case we can see this:

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 we can assume that

Then for each vertex and we can define and

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

we have that:

And with this we have the maximization problem solved.  

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

i wish i could u

step-by-step explanation:

i wish i could u