Determine and certify maximum flow practice questions | General Mathematics (Year 12, VCE Units 3 & 4, Flow, matching and scheduling, Flow networks)

Maximum flow certificates

A feasible flow obeys every capacity and conservation condition in the directed network. When its value equals the capacity of a cut, the two certificates prove the maximum flow

F=C(S,T)\Rightarrow F\text{ is the maximum flow}

Respect every capacity Flow on an edge is non-negative and cannot exceed that edge's capacity \(\displaystyle 0\leq f(e)\leq c(e)\)
Conserve flow At every intermediate vertex, incoming flow equals outgoing flow \(\displaystyle \sum f_{\mathrm{in}}=\sum f_{\mathrm{out}}\)
Total the source flow The flow value is the total flow leaving the source \(\displaystyle F=8+5=13\)
Match the cut certificate An equal feasible-flow value and cut capacity give the maximum-flow conclusion \(\displaystyle F=13,\quad C(S,T)=13\quad\Rightarrow\quad F=C(S,T)\)

Worked example

A directed network has capacities 7, 5, 7, 5 and 12 on the listed edges. Find and certify its maximum flow

S\to A:7,\quad S\to B:5,\quad A\to M:7,\quad B\to M:5,\quad M\to T:12

\(\displaystyle f(S,A)=7,\quad f(S,B)=5\)Use the full capacity on each source edge for the proposed feasible flow
\(\displaystyle F=7+5=12\)The total flow is the amount leaving the source
\(\displaystyle f(A,M)=7,\quad f(B,M)=5\)These flows conserve the 7 and 5 units entering A and B
\(\displaystyle 7+5=12=f(M,T)\)The two flows entering M are conserved by the flow of 12 leaving M
\(\displaystyle C(\{S,A,B,M\},\{T\})=12,\quad F=C=12\)The cut contains the edge M to T with capacity 12, so equal certificates prove a maximum flow of 12

Common mistakes

Adding source capacities without checking bottlenecks

✕\(\displaystyle F=8+5=13\)✓\(\displaystyle F=4+5=9\)

A source edge can carry its full capacity only when the downstream route can also carry that flow

Using a shared edge twice

✕\(\displaystyle 6+6=12\)✓\(\displaystyle 6\)

A shared edge has one capacity, so its capacity cannot be allocated in full to two incoming routes

Calling one edge the network maximum

✕\(\displaystyle F=3\)✓\(\displaystyle F=3+4=7\)

A network can carry flow on several routes, so one individual edge is not a complete cut certificate

Difficulty levels

introFinds a maximum flow on disjoint route channels by inspection

standardUses conservation at a merge or split to construct a feasible flow

challengeHandles a shared capacity and a reverse crossing edge with a supplied cut

examCompletes a compact flow certificate and selects the equal-capacity cut

Questions about this topic

Why does an equal flow and cut value prove maximum flow?+

The feasible flow shows that value can be achieved, while the cut shows that no larger value can cross the network. Equal values therefore give the maximum

Why cannot all capacity leaving the source always be used?+

A downstream edge or shared section may have less capacity, or an intermediate vertex may fail conservation if all source capacity is used

What is flow conservation at an intermediate vertex?+

It means the total flow entering the vertex equals the total flow leaving it. Flow is not created or lost at that vertex

Can I use a calculator?+

A calculator is allowed unless a question is marked no calculator

Which year level and chapter is this?+

Year 12, VCE Units 3 & 4, General Mathematics, chapter 14: Flow, matching and scheduling

In this chapter

Read and model a directed flow network 14A Flow networks: Validate a cut and calculate its capacity 14A Flow networks: Determine and certify maximum flow Represent and solve a small bipartite matching problem Find an optimum assignment with the Hungarian algorithm 14B Matching and assignment: Validate a cut and calculate its capacity Translate between precedence data and an activity network Complete a critical path analysis Reduce project duration subject to crash limits and costs 14C Scheduling and critical path analysis: Determine and certify maximum flow