Find Max Flow and Min Cut Please show all work Now use the s

Find Max Flow and Min Cut. Please show all work

Now use the same network as for Problem 1, but now consider the weights on the arcs to be capacities and find the max flow through the network. Indicate the min cut.

Solution

Hi,

To start calculating we need to choose a source and sink node a will be the source. So, the total pusing wil be sum of all pamping edges of a i.e., 8+5+6+4 = 23.

The max capacity of sink j will be sum of all edges capacity 7+8+9+5=29

but there are cutting edges in the network that means there are some edges who capacity is low can not allow all the flow throw it.

we have several algorithms to calculate max flow.Most of them are brute force kind of algorithms

one of them is Fore-Fulkerson

1)find an augmenting path

2)compute the bottleneck capacity

3)augment each edge and the total flow

So,

we will follow the approch like this

1) start with edge a->e total capacity is 8 and 8 will go throw e->i edge and then 7 will reach the sink i->j

2)start with edge a->d total capacity is 5 and 5 will go throw d->f edge and then 5 will reach the sink f->j

3)start with edge a->c total capacity is 6 and 6 will go throw c->g edge and then 6 will reach the sink g->j

4)start with edge a->b total capacity is 4 and 4 will go throw b->h edge and then 4 will reach the sink through h->k and k->j edge

max flow reaching sink would be 7+5+6+4 = 22

the cut min cut off we will the (capacity of source - max flow)= 23-22 =1

Any further clarification required pelase comment below