Question

For the following network, with edge capacities as shown, find the maximum flow from S to T, along with a matching cut.

Short answer

The maximum flow is obtained with the residual capacity 13 and the matching cut is{S,C,F} and {A,B,D,E,G,T}

Step-by-step solution

Step 1:

Choose the augmenting path as S -> A -> D -> G -> T and the edge, which has the lowest capacity along the path, is A -> D andit has the capacity 4.

The following diagram represents it:

In the above diagram,

Left side is the current path and right side is the residual path.

The residual capacity is 4.

Subtract 4 from the capacity of the forward edge. Therefore, its capacity 6 now becomes 2 and the capacity of the reverse edge becomes 4.

Subtract 4 from the capacity of the forward edge. Therefore, its capacity 4 now becomes 0 and the capacity of the reverse edge becomes 4.

Subtract 4 from the capacity of the forward edge. Therefore, its capacity 5 now becomes 1 and the capacity of the reverse edge becomes 4.

Subtract 4 from the capacity of the forward edge. Therefore, its capacity 12 now becomes 8 and the capacity of the reverse edge becomes 4.

Step 2:

Choose the augmenting path as S -> A -> B -> E -> G -> T and the edge, which has the lowest capacity along the path, and it has the capacity 2.

The following diagram represents it:

In the above diagram,

Left side is the current path and right side is the residual path.

The residual capacity is 2.

Subtract 2 from the capacity of the forward edge. Therefore, its capacity 2 now becomes 0 and the capacity of the reverse edge becomes 6 from 4.

Subtract 2 from the capacity of the forward edge. Therefore, its capacity 2 i now becomes 0 and the capacity of the reverse edge becomes 2.

Subtract 2 from the capacity of the forward edge. Therefore, its capacity 20 now becomes 18 and the capacity of the reverse edge becomes 2.

Subtract 2 from the capacity of the forward edge. Therefore, its capacity 10 now becomes 8 and the capacity of the reverse edge becomes 2.

Step 3:

Subtract 2 from the capacity of the forward edge. Therefore, its capacity 8 now becomes 6 and the capacity of the reverse edge becomes 6 from 4.

Choose the augmenting path as S -> B -> E -> G -> T and the edge, which has the lowest capacity along the path, and it has the capacity 1.

The following diagram represents it:

In the above diagram,

Left side is the current path and right side is the residual path.

The residual capacity is 1.

Subtract 1 from the capacity of the forward edge. Therefore, its capacity 1 now becomes 0 and the capacity of the reverse edge becomes 1.

Subtract 1 from the capacity of the forward edge. Therefore, its capacity 18 now becomes 17 and the capacity of the reverse edge becomes 3 from 2.

Subtract 1 from the capacity of the forward edge. Therefore, its capacity 8 now becomes 7 and the capacity of the reverse edge becomes 3 from 2.

Subtract 1 from the capacity of the forward edge. Therefore, its capacity 6 now becomes 5 and the capacity of the reverse edge becomes 7 from 6.

Step 4:

Choose the augmenting path as S-> C -> F -> T and the edge, which has the lowest capacity along the path, and it has the capacity 4.

The following diagram represents it:

In the above diagram,

Left side is the current path and right side is the residual path.

The residual capacity is 4.

Subtract 4 from the capacity of the forward edge. Therefore, its capacity 10 now becomes 6 and the capacity of the reverse edge becomes 4.

Subtract 4 from the capacity of the forward edge. Therefore, its capacity 5 now becomes 1 and the capacity of the reverse edge becomes 4.

Subtract 4 from the capacity of the forward edge. Therefore, its capacity 4 now becomes 0 and the capacity of the reverse edge becomes 4.

Step 5:

Choose the augmenting path as S -> C -> B -> E -> G -> T and the edge, which has the lowest capacity along the path, and it has the capacity 2.

The following diagram represents it:

In the above diagram,

Left side is the current path and right side is the residual path.

The residual capacity is 2.

Subtract 2 from the capacity of the forward edge. Therefore, its capacity 6 now becomes 4 and the capacity of the reverse edge becomes 6 from 4.

Subtract 2 from the capacity of the forward edge. Therefore, its capacity 2 now becomes 0 and the capacity of the reverse edge becomes 2.

Subtract 2 from the capacity of the forward edge. Therefore, its capacity 17 now becomes 15 and the capacity of the reverse edge becomes 5 from 3.

Step 6:

Subtract 2 from the capacity of the forward edge. Therefore, its capacity 7 now becomes 5 and the capacity of the reverse edge becomes 5 from 3.

Subtract 2 from the capacity of the forward edge. Therefore, its capacity 5 now becomes 3 and the capacity of the reverse edge becomes 9 from 7.

The maximum flow is obtained with the residual capacity 4+2+1+4+2=13

Then cut the partition into two, let it be “M” and “N”. Both should be a disjoint group where “S” should be in “M” and “T” should be in “N”.

LetM={S,C,F}andN={A,B,D,E,G,T}

Cut “M” is shown below:

Cut “N” is shown below:

Therefore, the maximum flow is obtained with the residual capacity 13 and the matching cut is {S,C,F} and {A,B,D,E,G,T}