Today we continue reading the flow networks. In particular, we look at the max flow min cut theorem. A cut of the flow network is a partition of its vertices into set S and T = V- S such that s belongs to S and t belongs to T. A minimum cut of the network is a cut whose capacity is the minimum over all cuts in the network. The max flow min cut theorem states the following:
1) f is a maximum flow in network.
2) there are no augmenting paths in the residual network.
3) the magnitude of the flow is the capacity of the cut for some cut (S,G)
This is proved by contradiction. The first implies the second. If there is an augmenting path in the residual network while there is a maximum flow in the network, the maximum flow can be exceeded with the augmentation. The second implies the third because if the residual network does not have any flows  the a cut between vertices s and t that do not have a path will have only forward flow and no reverse flow which implies it is the capacity.
The Ford Fulkerson method makes use of this property.  In each iteration of the method, an augmenting path p is found and used to modify the flow f. The residual capacity of that path is found and augmented to the flow. For each edge u,v in this path p, if it already exists in the edges E, we add the residual capacity in the forward direction or reduce it in the reverse direction.  In other words, each edge encountered is either an edge in the original network or its reversal.  The algorithm repeatedly finds paths until there are no more. At that point, we have maximum flow.
This is written as :
Ford-Fulkerson(G, s, t):
for each edge (u,v) belonging to G, E
      (u,v).f = 0
while there exists a path p from s to t in the residual network Gf
      cf(p) = min{cf(u,v): (u,v) is in p}
      for each edge (u,v) in p
            if (u,v) belongs to E
                (u,v).f = (u,v).f + cf(p)
            else (v,u).f = (v,u).f  - cf(p)

#puzzle
A car has 4 tyres and 1 spare tyre. Each tyre can travel a maximum distance of 20000 miles before wearing off. What is the maximum distance the car can travel before you are forced to buy a new tyre? You are allowed to change tyres (using the spare tyre) unlimited number of times.

The idea is to use all the tyres to the full. So we rotate the spare tyre in each of the four positions. This gives us a rotation at every 5000 miles and the total distance traveled as 25000 miles.

#codingexercise
Find two numbers with a given sum in an array
void PrintPairsWithSum(List<int> num, int sum)
{
assert(num.all(x => x < sum));
var h = new Hashtable();
for (int I = 0; I < num.count; i++)
{
 int other = sum - num[I];
 if (other > 0 && h.Contains(sum-num[I]) && h[sum-num[I]] == 1)
      Console.Write(num[I], other);
h[num[I]]  = 1;
}
}
Int getTurningPoint(List<int> num)
{

For(int i = 1; i < num.count; i++)
     If (num[i-1] < num[i])
     Return i;
Return -1;

}