Use the maximum flow algorithm that we leadin in class to de

Use the maximum flow algorithm that we lead-in in class to determine the maximum that is network. Show your worth the labels on each node and then did in class. Specifically, for each iteration list the labels on each node and then how much is pushed through the network and what path was used. Do this for each intention.

Solution

To find the maximum flow algorithm we have to go from S to T

To find the augmented flow that is only forward flow from S to T

S ---> A ----> E---> T which gives count 12.

Augmented path: forward edges flow(u,v) < capacity(u,v)

flow can be increased.

Backward edges flow(u,v) > 0

flow can be decreased.

Maximum flow theorem:

A flow has maximum value if and only if it has no augmenting path.

To find the maximum flow initialise the network with a null flow.

send one unit of flow through the network until you find no augmented flows in the network.

S---> A ----> E ---> T

S----> A ----->D----->T

S-----> B----->D------> T

S------> C---->T

S----> C-----> B----> D----> T

on initialising the path with zeros send one unit flow every time until we get no augmented path.

Thus we can achieve maximum flow from the network.