Discrete Mathematical Structures by Pearson

Topics in Graph Theory 10-55

The edges (a, b), (b, t), (s, c), (c, d), (c, b), (a, d), and (d, t) are unsaturated. The slack for edge

(a, b) is c(a, b) − f (a, b) = 20 − 15 = 5.

Similarly, the slack for other unsaturated edges can be calculated. At every intermediate

vertex, flow conservation law is satisfied.

10.18.1 Cut-Set and Capacity

In the transport network N(V, E), let us consider a cut-set with respect to vertices s and t ignoring

the directions of edges. A cut-set with respect to s and t is a cut that separates source s and sink t.

Let (S, T) denote a cut that partitions the set V of vertices into two subsets S and T where S

contains the source s and T contains the sink t. The capacity of cut C(S, T) is the sum of capacities

of all ...