Show that in a network G with capacities all equal to 1, the capacity of a minimum cut set (S, T) equals the minimum number q of edges whose deletion destroys all directed paths s ? t. (A directed path v ? w is a path in which each edge has the direction in which it is traversed in going from v to w.)

Transcribed Image Text:

4 5 6 3 3 4 5 7 5 3 6 8 4 (8) to