Model connectivity and bottlenecks with conservation

Try

A source sends material to a destination through two intermediate locations. One route can carry at most 4 units per hour and the other at most 6. If they share no limiting edge, the total can reach 10. If both pass through a final edge of capacity 7, that shared connection changes the answer.

A flow model records a graph, edge capacities, a source and a sink. At every other node, inflow equals outflow unless storage or production is explicitly included.

Predict

Predict whether increasing the first route’s capacity from 4 to 8 helps when the shared final capacity remains 7. Identify a global obstruction rather than looking only at the changed edge.

Experiment

Use the source-side cut just before the shared final edge. Every unit reaching the sink must cross it.

Route capacity total	Shared final capacity	Maximum possible throughput
4+6=10	7	7
8+6=14	7	7
8+6=14	12	12

For each row, construct a feasible split of flow across the two routes. The capacity bound alone gives an upper bound; an attaining feasible flow is the second half of an optimality certificate.

Understand

For a directed edge e, impose 0≤fₑ≤cₑ. Summing node balances over any set containing the source but not the sink cancels internal edges. The flow value equals outgoing crossing flow minus incoming crossing flow and is therefore at most the sum of outgoing capacities. This proves the flow-cut inequality independently of any search algorithm.

If a feasible flow and a cut have equal values, the flow is maximum and the cut is minimum. A general max-flow/min-cut theorem guarantees such certificates for finite networks, but a particular displayed pair can be checked directly. The combinatorics unit develops the graph-theoretic proof and algorithms; here the modeling task is deciding whether the network and capacities represent the question.

Capacity units must match. Adding a daily processing limit to an hourly transport limit without conversion is meaningless. A static capacity may be a simultaneous steady limit, a scheduled availability or an empirical average; these interpretations lead to different feasible sets. If edge capacities fluctuate together, treating every edge as independently available at its individual maximum can overstate achievable throughput.

Static maximum flow also omits delay. Two networks can have equal throughput but very different travel times and queues. For a waiting-time question, introduce time-expanded nodes, dynamic storage or a queue model. The correct abstraction depends on the output in the original question contract.

Apply

Create a network with at most six nodes, explicit capacities and one candidate intervention. Supply a feasible flow and a matching cut before and after the change. Explain whether your result concerns throughput, latency or reliability. If the intervention has no effect, identify the remaining cut instead of calling the computation unsuccessful.

Continue

Optimization generalizes this certificate-based reasoning to decisions with costs and resource constraints. A feasible proposal and a valid bound make a recommendation more defensible than a solver output alone.