D2 3.1 - Cuts and their capacity

D2 3.1 - Cuts and their capacity

You will distinguish flow from capacity, describe directed cuts precisely, and use cut capacities to bound the flow through a network.

Read a directed flow network

A cut crosses three pipes with capacities 7,9,37,9,3 litres per second. Could its capacity be only 1616, rather than 1919? Yes: the direction of each pipe matters.

We will use a small network to see why. First separate the current amount flowing from the maximum amount a pipe could carry.

You already know

A non-negative quantity is at least zero. Rates measured in the same units can be added and compared.

A graph consists of nodes, also called vertices, joined by arcs or edges. A network attaches numerical information to those connections. In a directed network an arrow specifies an arc's permitted direction. A directed path follows a sequence of nodes without repeating a node, using joining arcs in their arrow directions. Arcs crossing on the page are not joined unless a node is marked at the crossing.

All networks here have directed arcs. The source S supplies flow and the sink T receives it. Other nodes pass flow on without producing, consuming or storing it.

Capacity, feasible flow and flow value

An arc's capacity is its maximum permitted rate. With no positive lower limits, its actual flow satisfies

0≤fuv≤cuv0\le f_{uv}\le c_{uv}

At every node other than source and sink, total inflow equals total outflow. A flow satisfying these conditions is feasible.

The value FF is net flow leaving the source, equivalently net flow entering the sink. In the examples S has no incoming arcs and T has no outgoing arcs, so simply total the flows leaving S or entering T.

The following network has capacities and one feasible current flow. All quantities are litres per second.

Directed arcCapacityCurrent flow
S→AS\to A8866
S→BS\to B7755
B→AB\to A3322
A→TA\to T9988
B→TB\to T4433

At A, 6+2=86+2=8; at B, 5=2+35=2+3. The source sends 6+5=116+5=11, and the sink receives 8+3=118+3=11. The capacities leaving S total 1515, but the current flow value is 1111, not 1515.

[DIAGRAM: asset_name: A directed network with a backward crossing arc; asset_slug: 9fm0-d2-185-directed-cut; caption: The cut separates S and A from B and T; only SB and AT add to its capacity.; description: Directed arcs SA capacity8 flow6, SB7 flow5, BA3 flow2, AT9 flow8 and BT4 flow3, with capacities plain and flows circled; a dashed cut crosses SB,BA,AT, and the source side containing S,A is shaded.]
The cut separates S and A from B and T

A cut is a partition of the nodes, rather than a choice of whichever arcs happen to look full. Put S on one side and T on the other; then examine every arc joining the two sides.

Key idea

Capacity describes a limit; flow describes what is currently happening. Check conservation at intermediate nodes before treating a collection of arc flows as a feasible network flow.

Use the source and sink totals to read the current value.

Count only arcs going from the source side to the sink side

Describe a cut by two node sets X,YX,Y, where S∈XS\in X, T∈YT\in Y, and every node belongs to exactly one side. Removing all arcs between the two sets separates the source from the sink.

Capacity of an ordinary directed cut

With non-negative flows and no positive lower capacities,

c(X,Y)=∑u∈Xv∈Ycuvc(X,Y)=\sum_{\substack{u\in X\\v\in Y}}c_{uv}

Add capacities only for original arcs directed from XX to YY. Arcs directed from YY to XX do not contribute to this capacity.

Not in the formula booklet: learn it.

Drawn cuts can bend. Label the two node sets or list the relevant directed arcs so the partition is clear. Do not count a pipe twice because a poorly drawn curve crosses it twice; the node partition defines the cut.

Worked example 1: a backward arc does not add capacity

Question. For the network above, find the capacity of the cut

X={S,A},Y={B,T}X=\{S,A\},\qquad Y=\{B,T\}

Plan. Check the endpoints and arrow of every arc crossing between the sets.

Crossing arcDirection relative to the cutContribution
S→BS\to BX→YX\to Y77
A→TA\to TX→YX\to Y99
B→AB\to AY→XY\to X00

SA lies wholly in X and BT wholly in Y. Therefore

c(X,Y)=7+9=16c(X,Y)=7+9=16

Why ignore capacity 33 on BA? It carries flow back towards the source side. It cannot increase the amount that the forward-crossing pipes can send out of X.

Answer. The cut capacity is 1616 litres per second.

Check. The current net flow across the boundary is 5+8−2=115+8-2=11, the network flow value. Adding all three capacities would give 1919, which counts the backward arc incorrectly.

Worked example 2 changes only A's side of the cut, moving A from X to Y. The network and all capacities remain unchanged.

Continue this lesson.

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

Create free account