Past exam of the mathematics course of the University of Cambridge / 2019 / ib / Paper 4 / 20H / b / i

Table of contents
- Solution i

Solution

Starting from zero, one valid run of the Ford-Fulkerson algorithm augments along

S \to a \to d \to T S \to b \to d \to T S \to b \to e \to T S \to c \to e \to T by 1, by 2, by 1, by 4.

The resulting nonzero edge flows are

edge flow S a 1 S b 3 S c 4 a d 1 b d 2 b e 1 ce 4 d T 3 e T 5

and they obey every capacity constraint and every flow-conservation equation. The flow value is

∣ f ∣ = 1 + 3 + 4 = 8 .

 Ancestors (11)

 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