Examiner's comment
Part (f) discriminated well with very few proving that the flow was optimal. To assist for future series please find below a way in which candidates can set out such a proof: • It is best to state (and not just draw) a cut (that passes through saturated arcs that are directed from the source set to the sink set of nodes together with any arcs with zero flow that are directed from the sink set to source set) - so for this network as a list of arcs this was BE, FE, GE, GH, GT and DT or as set of nodes { } { } S,A,B,C,D,F,G , E,H,T . • State the capacity of this cut and hence what this implies about the minimum cut e.g. the value of this cut is 53 which implies that the minimum cut 53 • State the value of the flow through the network after augmentation and what this implied about the maximum flow e.g. the current flow through the network is 53 which implies that the maximum flow is 53 • Conclude the proof by referring to the maximum flow-minimum cut theorem e.g. the min. cut is 53 and the max. flow is 53 but by the maximum flow-minimum cut theorem the max. flow is equal to min. cut therefore the maximum flow is 53 and therefore the flow is indeed optimal.