Past exam of the mathematics course of the University of Cambridge / 2017 / ib / Paper 4 / 20H / c

Table of contents
- Solution c

Solution

Reading the arrows directly from the original PDF gives, in particular,

c \to a

and

e \to d

. Starting from zero flow, use the following augmenting paths and bottlenecks, in order:

$s \to a \to d \to t$ : $6$ .
$s \to b \to e \to t$ : $5$ .
$s \to c \to e \to t$ : $5$ .
$s \to b \to c \to d \to t$ : $2$ .
$s \to b \to c \to e \to t$ : $1$ .

Each path is available in the current residual network. The resulting nonzero edge flows are

f_{s a} f_{a d} f_{c d} = 6, = 6, = 2, f_{s b} f_{b c} f_{ce} = 8, = 3, = 6, f_{sc} f_{b e} f_{d t} = 5, = 5, = 8, f_{e t} = 11.

The flows on

c \to a

and

e \to d

are zero. Capacity constraints and flow conservation hold at each interior vertex; net source outflow is

6 + 8 + 5 = 19

.

Take

S = {s, a, b, c}

. Its outgoing edges are

a \to d

,

c \to d

,

b \to e

,

c \to e

, with total capacity

6 + 2 + 5 + 6 = 19

. Thus the matching flow and cut of a flow network certificates give

maximum flow value = 19, minimum cut ({s, a, b, c}, {d, e, t}) .

These are also exactly the source-reachable vertices in the final residual network. The original drawing below labels each edge by flow/capacity; the highlighted edges realise the minimum cut of a flow network.

Figure 1.
A maximum flow and its edge capacities
. Verified maximum flow, with each arrow labelled flow/capacity and the minimum cut marked in orange.

 Ancestors (10)

 View article source

 Discussion (0)

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version