ANONYMOUS wrote:

I have a question regarding the Lecture 16, on the video recording in LMS, timestamp 1:23:11 It was said that the cut on the saturated graph shown as the example would be

{S,A,C,D} and {B,T}

And it was said that the Source Vertex could reach A C D however could not reach B. I do not understand how this was obtained as the direct edges from Source Vertex only reached A C, not D.

Reachability is transitive. s is able to reach d via c. The core point is that the s side of the cut will be exactly those vertices that are reachable from s through the residual graph. That is, the vertices to which s could push flow. This because it means that we can get flow to any vertex in the s-component, and so if any of them have an (unsaturated) edge to something in the t-component, then we could push more flow across the cut.