The University of Hong Kong · FACULTY OF MATHEMATICS

DASE7034 Chap.8 Maximum Flow and Minimum Cuts

- one subject, every graph, every model, every mark
5 Chapters4-page Bible
Our own words - no uploaded lecturer files
Updated for this semester
Chapter 8 of 12 · DASE7034

Maximum Flow and Minimum Cuts

Maximum flow sends the greatest feasible quantity from a source to a sink through capacitated arcs. Residual capacity records unused forward capacity and cancellable reverse flow, allowing augmenting paths to revise earlier choices.

When no augmenting path remains, residual reachability gives a cut; equality between its capacity and the flow certifies optimality.

Separate capacity from realised flow

Each directed arc has a capacity that limits the amount sent along it and a flow that must lie between zero and that capacity.

At every intermediate node, total inflow equals total outflow; only the source creates net flow and only the sink absorbs it. The flow value can be measured as net departure from the source or net arrival at the sink, which should agree.

Arc direction and units must remain explicit because an arrow can represent a pipeline, road direction or information channel with different operational meaning.

Use the residual network to revise choices

For every original arc, the residual network contains forward capacity equal to unused capacity and reverse capacity equal to the current flow.

A source-to-sink residual path permits augmentation by its smallest residual value, the bottleneck. Add that value on forward arcs and subtract it where the path uses a reverse arc.

Reverse residuals are essential: they allow an earlier routing choice to be cancelled and redirected, so a locally attractive first path does not trap the procedure at a suboptimal flow.

Construct a cut certificate

When no augmenting path remains, mark all nodes reachable from the source through positive residual arcs. Those nodes form the source side of a cut and the remaining nodes form the sink side.

Cut capacity is the sum of capacities of original arcs directed from the source side to the sink side; arcs in the opposite direction are not added.

If the cut capacity equals the current flow value, weak duality and the max-flow min-cut theorem certify that both are optimal.

Interpret bottlenecks without overclaiming

A minimum cut identifies a set of arcs whose combined capacity limits the present network, but several minimum cuts can exist. Increasing one cut arc may merely expose another bottleneck, so recompute the maximum flow after any capacity change.

Multiple maximum-flow routings can also achieve the same value, leaving room for secondary goals such as cost, fairness or robustness. A recommendation should state the current flow, its cut certificate, the proposed capacity intervention and the assumptions about simultaneous capacity, conservation and time period.

In this chapter

What this chapter covers

  • 01

    Source and sink structure

  • 02

    Arc capacity and conservation

  • 03

    Residual networks

  • 04

    Augmenting path bottlenecks

  • 05

    Maximum-flow minimum-cut certificate

Worked example · free

Augment by a path bottleneck

Q [6 marks]. This weighting is for AskSia practice and not an official University marking scheme. A residual path has capacities 4, 7 and 3. Update the flow.
Residual capacities determine the next augmenting path.Residual capacities determine the next augmenting path. The bottleneck is the smallest residual value on the selected source-to-sink path, not the smallest original capacity everywhere.suvtr=4r=3r=5r=2
Residual capacities determine the next augmenting path. The bottleneck is the smallest residual value on the selected source-to-sink path, not the smallest original capacity everywhere.
  • 2Identify the minimum residual capacity.
  • 2Augment every path arc by that amount.
  • 2Update reverse residual capacities.
The bottleneck is three, so augment three units along the entire path. Subtract three from each forward residual and add three to each corresponding reverse residual. Recheck conservation at intermediate nodes before searching for another path. The marks assigned to these steps are AskSia revision aids, not the University's published assessment scheme.
Sia tip — The bottleneck belongs to the selected path, not to the smallest capacity anywhere in the network.
Glossary

Key terms

Residual Network
A network showing how much additional net flow can be sent or cancelled in each direction.
Augmenting Path
A source-to-sink path whose residual capacity is positive on every arc.
Cut Capacity
The sum of capacities on forward arcs crossing from the source side of a cut to the sink side.
FAQ

Maximum Flow and Minimum Cuts FAQ

Why are reverse residual arcs needed?

They allow later augmentations to cancel part of an earlier flow and reroute it. Without reverse capacity, a locally attractive first path can trap the algorithm below the true maximum.

Does a saturated arc always belong to a minimum cut?

No. Many arcs can be saturated without limiting total source-to-sink throughput. The minimum-cut certificate identifies the particular boundary whose forward capacity equals the maximum flow.

How is a node capacity represented?

Split the node into an in-node and an out-node joined by an arc whose capacity equals the node limit. Original incoming arcs enter the first and outgoing arcs leave the second.

Study strategy

Exam move

On a small network, keep separate tables for current flow and residual capacity. After each augmentation, verify source value, sink value and conservation at every intermediate node. At termination, list reachable residual nodes and recompute the cut capacity directly. Use a two-line record for every original arc: current flow over capacity and forward plus reverse residual values.

For each augmenting path, list its residual arcs, circle the smallest residual as the bottleneck and update forward and reverse entries together. Then check source departure, sink arrival and flow conservation at each intermediate node. At termination, perform a residual reachability search from the source and write the two node sets.

Calculate cut capacity using only original arcs directed from the reachable side to the unreachable side; do not add reverse-crossing arcs. Compare that capacity with the flow value as the optimality certificate. Finally, increase one cut arc and resolve the network instead of assuming throughput rises by the same amount.

Note any new minimum cut or alternate maximum-flow routing, and connect the result to the operational time period and capacity units represented by the arcs.

Working through Maximum Flow and Minimum Cuts in DASE7034? Sia is AskSia’s AI Mathematics tutor — ask any DASE7034 Maximum Flow and Minimum Cuts question and get a clear, step-by-step explanation grounded in how DASE7034 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.

A+Everything unlocked
Unlocks this Bible + all 52 of your subjects at The University of Hong Kong, plus 1,000+ more Bibles across the AskSia library.
Sia - your DASE7034 tutor, unlimited, worked the way the exam marks it
The full 4-page Bible + practice bank with worked solutions
Chrome extension - sync your LMS so Sia knows your deadlines
Bilingual EN / Chinese on every Bible and every Sia answer
$0.99 Trial
30-day money-back · cancel in one tap · how it works