Instead of editing the RMarkdown source file for this assignment, you can just draw diagrams on paper and scan them to PDF using a scanning app, or you could produce a PDF file some other way. Upload the .pdf to Canvas.

Consider the following flow network \(G\). Values of a flow \(f\) and edge capacities are given as “value/capacity” pairs.

  1. Draw the residual graph \(G_f\).

  2. Find a path from \(s\) to \(t\) in \(G_f\), and determine \(F\), the maximum amount of flow through this path. (Choose this path so that \(F\) is as large as possible.)

  3. Augment the flow \(f\) using the augmenting path you found in #2 to obtain a new flow \(f'\).

  4. Repeat steps 1-3 (update the residual graph, find an augmenting path, augment the flow) as many times as necessary to obtain a maximum flow in \(G\).

  5. Show that your maximum flow is actually a maximum flow by finding a cut whose capacity equals the total value of the flow.

  6. Does your minimum cut correspond to the set of vertices that are reachable from \(s\) in the residual graph?