Determine and certify maximum flow

What is the first decision when proving a maximum-flow value?

Here arrows represent one-way shuttle services. Can you travel from C to A using only the displayed services?

Vary only the B→T capacity through 9,10,11. For each setting compare the two displayed cut bounds. All other capacities remain fixed

Why does raising B→T from 10 to 11 give no further gain?

From network connections to capacities

The reused Year 10 direction check distinguishes a connected-looking drawing from a usable directed route. This lesson adds per-time capacities. Drawing lengths and unmarked crossings still have no capacity meaning

1. 1Respect every capacity Flow on an edge is non-negative and cannot exceed that edge's capacity \(\displaystyle 0\leq f(e)\leq c(e)\)
2. 2Conserve flow At every intermediate vertex, incoming flow equals outgoing flow \(\displaystyle \sum f_{\mathrm{in}}=\sum f_{\mathrm{out}}\)
3. 3Total the source flow The flow value is the total flow leaving the source \(\displaystyle F=8+5=13\)
4. 4Match 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)\)

Construct the model and audit a feasible flow

A hypothetical tray-handling system sends trays from loading point S to packing point T through junctions A and B. Separate one-way conveyors have capacities S→A 8, S→B 7, A→B 4, B→A 2, A→T 5 and B→T 9 trays per hour. Assume steady operation, enough trays supplied at S, no losses or storage at A/B, independent channel capacities and no unmodelled shared equipment limits. These are invented planning values, not measured performance

1. 1Represent and distinguish Construct a labelled directed graph and complete capacity table from the description, including both A→B and B→A. State the source, sink, units and assumptions. Calculate the bottleneck capacities of routes S→A→T, S→A→B→T and S→B→T. Explain why their independent route maxima cannot simply be added
2. 2Construct and verify Propose a complete edge-flow allocation, including zero-flow edges. Check 0≤flow≤capacity on each edge, conservation separately at A and B, and equality of total source outflow and sink inflow. Produce a second different feasible flow to show that capacities alone do not specify a unique allocation
3. 3Produce an independent record Choose a representation and checking method before opening the model response. Save your labelled directed graph, complete edge-capacity and edge-flow tables, every conservation equation, source-side cut sets, actual tool formulas or commands, alternative case and reasoned conclusion. These independent constructions and external-tool operations are self/teacher-reviewed, not automatically marked by the short checks

Model response: Construct the model and audit a feasible flow

Compare the complete model and argument, not only a final number or selected option

1. 1Directed representation and bottlenecks The six directed edge capacities, in the stated order, are (8,7,4,2,5,9). S has no incoming edge and T no outgoing edge. Route bottlenecks are min(8,5)=5, min(8,4,9)=4 and min(7,9)=7. Their sum 16 is not a feasible simultaneous allocation: S→A would carry 5+4=9>8 and B→T would carry 4+7=11>9. A→B and B→A must not be merged into a single undirected capacity 6.
2. 2Complete feasible witness Assign (S→A,S→B,A→B,B→A,A→T,B→T)=(8,6,3,0,5,9). Every entry is within its capacity. At A, incoming 8+0 equals outgoing 3+5=8. At B, incoming 6+3 equals outgoing 0+9=9. Source outflow 8+6=14 equals sink inflow 5+9=14 trays/hour. The reverse conveyor is available but unused; an unused channel has flow 0, not capacity 0.
3. 3Non-uniqueness and partial certificates A second feasible maximum allocation is (7,7,2,0,5,9), also of value 14. A smaller integer allocation is (6,6,1,0,5,7), of value 12. The all-zero allocation is feasible but not maximum. If fixed entries specify S→B=6, B→A=0, A→T=5 and B→T=9, conservation uniquely gives A→B=3 and S→A=8. Without the fixed entries, those two particular values are not forced. For indivisible trays, the displayed hourly allocations are integer counts; do not interpret arbitrary fractional tray counts as literal observations

What does the label 2 on B→A mean?

Given information

\(\displaystyle c(SA)=8,\quad c(AB)=4,\quad c(BT)=9\)

Find the bottleneck capacity of the route S→A→B→T, in trays per hour

Given information

\(\displaystyle f(SB)=6,\ f(BA)=0,\ f(AT)=5,\ f(BT)=9\)

Complete the fixed certificate: find the A→B flow, in trays per hour

Given information

\(\displaystyle f(AB)=3,\ f(BA)=0,\ f(AT)=5\)

Using that fixed certificate, find the S→A flow, in trays per hour

The routes S→A→T, S→A→B→T and S→B→T have individual bottlenecks 5, 4 and 7 trays per hour. Their edge capacities are S→A 8, A→T 5, A→B 4, S→B 7 and B→T 9. Why is 5+4+7 not a feasible simultaneous total?

Prove the maximum with both certificates

Use the network with capacities S→A 8, S→B 7, A→B 4, B→A 2, A→T 5 and B→T 9 trays per hour. A complete feasible allocation in that edge order is (8,6,3,0,5,9). A cut is specified by a set containing S and excluding T; its other side is the complement. The physical drawing of a curve is not the definition of a cut

1. 1Enumerate and prove List all source-side sets, identify every forward crossing edge for each, and calculate the cut capacities. For source side {S,A}, identify the reverse crossing edge that must be omitted. Select a minimum cut and combine it with your feasible allocation to prove the maximum. State what the two separate bounds establish
2. 2Reject an invalid argument Explain why source capacity 15 is not automatically attainable, why minimum individual capacity 2 is not the answer, and why the phrase minimum cut does not ask for the minimum feasible flow. Give a changed allocation that violates conservation even though its edge bounds all hold
3. 3Produce an independent record Choose a representation and checking method before opening the model response. Save your labelled directed graph, complete edge-capacity and edge-flow tables, every conservation equation, source-side cut sets, actual tool formulas or commands, alternative case and reasoned conclusion. These independent constructions and external-tool operations are self/teacher-reviewed, not automatically marked by the short checks

Model response: Prove the maximum with both certificates

Compare the complete model and argument, not only a final number or selected option

1. 1Complete cut inventory There are exactly 2²=4 source-side sets because A and B can each lie on either side. {S}: forward edges S→A,S→B total 8+7=15. {S,A}: forward S→B,A→B,A→T total 7+4+5=16; B→A points backwards and contributes nothing. {S,B}: forward S→A,B→A,B→T total 8+2+9=19. {S,A,B}: forward A→T,B→T total 5+9=14. The minimum cut capacity is 14.
2. 2Two bounds, one conclusion The feasible flow of 14 proves maximum≥14. Every feasible flow must cross the cut {S,A,B} with total forward capacity 14, proving maximum≤14. Hence maximum=14 trays/hour by the maximum-flow/minimum-cut theorem. Source capacity 15 is only another upper bound, while the unused reverse-edge capacity 2 is not a system bottleneck. Minimum cut means minimum among cut capacities, not minimum feasible flow; zero flow is possible
3. 3Conservation counterexample and verification Change only S→A from 8 to 7 in the first allocation, keeping S→B 6,A→B 3,B→A 0,A→T 5,B→T 9. Every edge remains within capacity but A receives 7 and sends 8, so this is not a feasible flow. A reproducible spreadsheet can store From,To,Capacity,Flow; check Flow≥0 and Flow≤Capacity in each row and calculate each internal balance with incoming SUMIF minus outgoing SUMIF. For a cut, sum Capacity only where From belongs to the source-side set and To does not. Keep all four cut records and actual formulas or commands; the final number alone is not the certificate

Given information

\(\displaystyle c(SB)=7,\ c(AB)=4,\ c(AT)=5,\ c(BA)=2\)

Find the cut capacity for source side {S,A}, in trays per hour

Given information

\(\displaystyle F_{\rm feasible}=14,\quad C(\{S,A,B\})=14\)

Use the equal certificates to state the maximum flow, in trays per hour

Which pair of facts proves an optimum?

Investigate upgrades and closure without holding the old bottleneck fixed

The original capacities are S→A 8, S→B 7, A→B 4, B→A 2, A→T 5 and B→T 9 trays per hour. Consider three separate changes, not cumulative changes: increase only S→A from 8 to 10; increase only B→T from 9 to 11; or close only A→B. Compare the achievable throughput in each case. Then vary B→T through 9,10,11 while holding every other original capacity fixed

1. 1Rebuild certificates For each changed model, supply a complete feasible-flow vector and an equal-capacity cut. Explain why one upgrade gives no gain, why another gives only a bounded gain, and why the closure still leaves a route but reduces maximum throughput. Do not interpret connectedness as unchanged capacity
2. 2Choose technology and report Choose a spreadsheet, calculator or short program, explain why it suits this small network, and record actual inputs, all four cut totals and feasibility checks. If graphing B→T capacity against maximum throughput, justify the displayed range and show the transition where a different cut becomes limiting. State a qualified planning conclusion and the real measurements missing from this hypothetical model
3. 3Produce an independent record Choose a representation and checking method before opening the model response. Save your labelled directed graph, complete edge-capacity and edge-flow tables, every conservation equation, source-side cut sets, actual tool formulas or commands, alternative case and reasoned conclusion. These independent constructions and external-tool operations are self/teacher-reviewed, not automatically marked by the short checks

Model response: Investigate upgrades and closure without holding the old bottleneck fixed

Compare the complete model and argument, not only a final number or selected option

1. 1Upgrades Increasing S→A to 10 leaves cut {S,A,B} at 14. The original witness still sends 14, so there is no gain. Increasing B→T to 11 instead permits (8,7,3,0,5,10), value 15; cut {S} remains 15, proving the new maximum 15. The two-unit edge upgrade adds only one unit of throughput, and B→T retains one unused unit because the source-side cut now limits flow. Neither result follows from increasing an edge alone
2. 2Closure Closing A→B removes that edge rather than reversing it. A witness in original edge order, with the closed entry shown as 0 for comparison, is (5,7,0,0,5,7), value 12. The cut {S,A} has only S→B 7 and A→T 5 crossing forwards, capacity 12; B→A 2 is still a reverse crossing and omitted. Thus maximum 12 is below 14 even though S can still reach T.
3. 3Complete bounded parameter record Let b be B→T capacity with all other capacities fixed. Cut capacities in order {S},{S,A},{S,B},{S,A,B} are 15,16,10+b,5+b. For b=9,10,11 their minima are 14,15,15. The flow (8,min(7,b−3),3,0,5,min(b,10)) certifies each of these three settings. A graph restricted to 9≤b≤11 shows the rise to 15 and then a plateau; it is not evidence for values outside the chosen range. The explorer displays this proved bounded relation, not a general maximum-flow algorithm
4. 4Qualified conclusion Under this steady, independent-capacity model, upgrading B→T from 9 to 11 raises the maximum from 14 to 15 trays/hour; the S→A-only upgrade does not improve throughput. This does not justify buying equipment: costs, measured rates, loading availability, shared machinery, downtime, storage and operating restrictions have not been modelled. If the actual capacity assumptions change, rebuild the graph and both certificates before making a recommendation

Given information

\(\displaystyle c(AT)=5,\quad c(BT)=9,\quad F_{\rm old}=14\)

After increasing only S→A to 10, give the maximum flow, in trays per hour

Given information

\(\displaystyle c(SA)=8,\quad c(SB)=7,\quad F_{\rm feasible}=15\)

After increasing only B→T to 11, give the maximum flow, in trays per hour

Given information

\(\displaystyle c(SB)=7,\quad c(AT)=5,\quad F_{\rm feasible}=12\)

After closing only A→B, give the maximum flow, in trays per hour