Standard 13: Max Flow 1: Definitions

Short description: Apply definitions of flow, capacity, residual; identify valid and invalid flows.

Full description

Given a max flow input instance and a flow, identify the capacity of edges, flow along edges, and residual capacity. Identify whether the flow is valid, and if not, explain which constraint is not satisfied.

Example problem

Exercise 1. An example graph. Source s, sink t, and capacities on the edges: c(s,v)=4, c(s,w)=9, c(w,v)=7, c(w,x)=3, c(v,x)=5, c(v,t)=2, c(x,t)=9.

On the above graph, which of the following flows are valid? If invalid, indicate which constraint is violated and why.

Part a:

f(s,v)=2, f(s,w)=3, s(v,x)=1, s(v,t)=2, s(w,v)=1, s(w,x)=2, s(x,t)=3.

Part b:

f(s,v)=2, f(s,w)=3, s(v,x)=3, s(v,t)=2, s(w,v)=3, s(w,x)=2, s(x,t)=5.

Part c:

f(s,v)=2, f(s,w)=5, s(v,x)=3, s(v,t)=4, s(w,v)=3, s(w,x)=2, s(x,t)=3.

Sample solution

Sample solution.

Part a: valid.
Part b: invalid. The flow constraint at $w$ is violated: the total flow in is 3, but the total flow out is 5.
Part c: invalid. The capacity constraint on $(v,t)$ is violated: $c(v,t) = 2$, but $f(v,t) = 4$.

Rubric

Rubric.

To pass, a solution must pass all parts.

To pass, a solution must follow the course requirements for writing.

To pass, a solution must give a correct answer for all three parts. For b and c, it must correctly identify a violated constraint and correctly say why it is violated.

The numerical rubric for this problem is:

4 (Pass, Near-Perfect): correct, clear, concise.
3 (Pass, Proficient): correct, possibly not fully clear or concise. Perhaps a correct answer but with a minor arithmetic mistake.
2 (Fail, Progress): may be incorrect on one or more of the parts. May give a much too verbose solution, or explanations may contain major mistakes.
1 (Fail, Wrong Track): Does not appear to be applying correct definitions.