DC1, DC2 - Flows and cuts

DC1, DC2 - Flows and cuts

A network can have plenty of capacity near its entrance and still struggle to deliver material at its exit. DC1 introduces directed capacities, feasible flows and the roles of sources and sinks. DC2 uses cuts to place an upper limit on delivery, while keeping capacity separate from the flow actually being sent.

Directed capacities

Two pumps can supply a total of 13 litres per second, but the only pipes entering the delivery tank have capacities 4 and 7 litres per second. Can the tank receive all 13 litres per second? To answer, we must read both the numbers and the directions in the network.

You already know that a network represents connections between nodes. A flow network adds arrows and limits: a pipe from AA to BB need not allow any movement from BB to AA. The picture records permitted movement, rather than geographical distances.

Directed capacity

An arc A→BA\to B permits flow from AA to BB. Its upper capacity cc is the greatest permitted flow on that arc. With no stated lower bound, its actual flow ff must satisfy 0≤f≤c0\le f\le c.

In an arc list, SASA abbreviates the directed arc S→AS\to A. For example, a pipe of capacity 8 L s−18\,\mathrm{L\,s^{-1}} may carry 0, 3 or 8 litres per second. It cannot carry 9, and it does not have to carry 8. An arc is saturated when its actual flow equals its upper capacity.

A label such as 3/83/8, when the diagram's key specifies “flow/capacity”, means actual flow 3 and upper capacity 8. AQA diagrams may instead circle the flow and leave the capacity uncircled. Read the key: a pair of labels may also mean lower and upper capacities, which is a different convention.

Oppositely directed arcs A→BA\to B and B→AB\to A are separate permissions. If both are present, each has its own capacity and flow. Drawing two opposite arrows does not double the capacity of either one.

Key idea

A capacity tells you what an arc could carry; its flow tells you what it currently carries. The arrow tells you the permitted direction.

Use all three pieces of information in this check.

Conservation and feasible flows

A junction cannot create or lose material in a steady flow model. If 8 litres enter every second, 8 litres must leave every second. This is a balance equation, just like balancing money entering and leaving an account whose balance stays fixed.

Feasible flow

A feasible flow obeys every arc's capacity constraints and conservation of flow at every intermediate node: total flow into the node equals total flow out. Sources introduce material and sinks remove it, so they are the exceptions to this balance rule.

Conservation uses actual flows. Adding capacities around a junction does not test conservation, because the pipes need not all be full. A flow may obey conservation and still exceed an arc capacity; both tests are necessary.

Worked example 1: completing a feasible junction

Question. Two arcs bring flows 5 and 3 into an intermediate node AA. Its outgoing arcs carry 2 and xx. The arc carrying xx has capacity 7; the three stated flows are within their own capacities. Find xx and decide whether the flow is feasible at AA.

Plan. Balance actual inflow and outflow, then compare the missing flow with its capacity.

5+3=2+xconservation at Ax=6subtract 20≤6≤7capacity check\begin{aligned} 5+3&=2+x && \text{conservation at }A\\ x&=6 && \text{subtract }2\\ 0&\le6\le7 && \text{capacity check} \end{aligned}

Answer. x=6x=6, and the flow is feasible at this junction.

Check. The completed outflow is 2+6=82+6=8, equal to the independently totalled inflow 8; every arc is within its limit.

Keep every flow the same but reduce just the capacity of the unknown arc. Conservation alone will no longer be enough.

Worked example 2: a balanced but impossible junction

Question. The same junction has incoming flows 5 and 3 and outgoing flows 2 and xx, but the arc carrying xx now has capacity 5. Can these flows be feasible?

Plan. Find the value conservation requires and test it against the changed upper limit.

x=5+3−2=6required by conservation6>5exceeds the new capacity\begin{aligned} x&=5+3-2=6 && \text{required by conservation}\\ 6&>5 && \text{exceeds the new capacity} \end{aligned}

Answer. No. The required flow is 6, which the outgoing arc cannot carry.

Check. Even at full capacity, total outflow could be only 2+5=72+5=7, below the fixed inflow of 8. The contradiction does not depend on rearranging the equation correctly.

At a whole-network level, check every intermediate node, not just the one containing an unknown.

Watch out

Wrong: “All flows are below their capacities, so the flow is feasible.” Correct: check conservation too. An intermediate node with inflow 8 and outflow 7 would be accumulating material, outside this steady model.

Now complete a new junction and check both conditions.

Sources, sinks and flow value

The value of a flow measures delivery through the whole network. Adding all the arc flows would count the same material repeatedly as it travels through successive pipes.

Source and sink

A source supplies flow to the network; a sink receives flow from it. In the usual single-source, single-sink network, the source SS has no incoming arcs and the sink TT has no outgoing arcs. The flow value is the total leaving SS, equal to the total entering TT. If incoming source or outgoing sink flows are permitted, use net outflow at the source and net inflow at the sink.

Identify these roles from the arrows and context. A node drawn on the left need not be a source. At every other node, conservation makes incoming and outgoing contributions cancel when you total the entire network. Only the net supply and net receipt remain. This explains why the two ways of calculating value agree.

Continue this lesson.

You’re previewing NovaLearn without an account. Create a free account to read the rest.

Create free account