Maximum flow of a graph and minimum capacity of a s-t cut

275 Views Asked by At

Question: Find the maximum flow and minimum capacity of a s-t cut of the following graph. The capacity on every edge is 1 . The continuous edges have a flow of 0 and the dotted straight edges have a flow of 1. enter image description here

Step 1. Flow=0 enter image description here

Step 2. Use the fact that dotted edges gave a flow of 1 and continuous edges have a flow of 2. Total Flow= 3 enter image description here

Step 3: Augmented path 1. Total flow= 4.

h enter image description here

Step 4: Augmented path 2. Total flow = 5. enter image description here enter image description here

Step5. There are no other augmented paths left. enter image description here

S-t cut of minimal capacity :

enter image description here

1

There are 1 best solutions below

9
On BEST ANSWER

I don't understand your proposed solution at all. According to your description, the flows along the dotted edges already stand at their capacity of $\ 1\ $, so how could the paths $\ \text{s}$$\rightarrow$$\text{1}$$\rightarrow$$\text{a}$$\rightarrow$$\text{v}$$\rightarrow$$\text{t}\ $,$\ \text{s}$$\rightarrow$$\text{2}$$\rightarrow$$\text{w}$$\rightarrow$$\text{t}\ $ or $\ \text{s}$$\rightarrow$$\text{5}$$\rightarrow$$\text{e}$$\rightarrow$$\text{y}$$\rightarrow$$\text{t}\ $ be flow augmenting?

Two flow augmenting paths would appear to me to be $\ \text{s}$$\rightarrow$$\text{b}$$\rightarrow$$\text{v}$$\rightarrow$$\text{a}$$\rightarrow$$\text{u}$$\rightarrow$$\text{t}\ $ and $\ \text{s}$$\rightarrow$$\text{4}$$\rightarrow$$\text{e}$$\rightarrow$$\text{5}$$\rightarrow$$\text{d}$$\rightarrow$$\text{t}\ $. Sending a flow of $\ 1\ $ along each of those paths will produce the set of flows represented in the following diagram:

enter image description here (with the same convention that the flow along all continuous edges is $\ 0\ $, and the flow along all dotted edges is $\ 1\ $).

The total flow from $\ s\ $ to $ t\ $ with this assignment is $\ 5\ $, and the total flow through the cut comprising the edges $\ \text{u}$$\rightarrow$$\text{t}\ $,$\ \text{v}$$\rightarrow$$\text{t}\ $,$\ \text{w}$$\rightarrow$$\text{t}\ $,$\ \text{d}$$\rightarrow$$\text{t}\ $ and $\ \text{y}$$\rightarrow$$\text{t}\ $ is also $\ 5\ $. Therefore the maximum flow through the graph from from $\ s\ $ to $ t\ $ is $\ 5\ $ and the edges $\ \text{u}$$\rightarrow$$\text{t}\ $,$\ \text{v}$$\rightarrow$$\text{t}\ $,$\ \text{w}$$\rightarrow$$\text{t}\ $,$\ \text{d}$$\rightarrow$$\text{t}\ $,$\ \text{y}$$\rightarrow$$\text{t}\ $ constitute a cut of minimum capacity.