8.2 Applications of Ford-Fulkerson

Question 1

What is a circulation network

Answer 1

Problem: determine if valid circulation exists
Node value = how much it consumes

Question 2

How to reduce a circulation problem to a maximum flow problem (and what algorithm to use)

Answer 2

Connect the source vertex to every ‘source’ (d<0), connect sink to every ‘sink’ vertex (c>0). Use Edmonds-Karp to check if sum of sources = - sum of sinks (ie valid circulation)

Question 3

What is a vertex flow network

Answer 3

Each vertex has a capacity

Question 4

How to solve a vertex flow network (using a gadget)

Answer 4

Split each vertex into an input and output vertex, with the edge capacity connecting them

Question 5

How to transform flow networks into linear programming

Answer 5

Obj: max flow (out of source)
Add all constraints:
1) Inflow = outflow for each edge (except s, t)
2) Edge capacities