D2 - Unit 2

Question 0

What is the maximum flow?

Answer 0

The most amount that can get through a network

Question 1

What is a cut?

Answer 1

A cut is a continuous line which separates the source S from the sink T. It does not pass through any nodes.

Question 2

What is the Maximum Flow - Minimum Cut theorem?

Answer 2

• The flow through the network can’t exceed the value of any cut.
• the maximum flow equals the value of the minimum cut.

Question 3

What are arcs carrying their full capacity called?

Answer 3

Saturated.

Question 4

How to find the maximum capacity

Answer 4

1. Find an initial flow that satisfies minimum capacities.
2. Allocate the minimum possible flows to each route from S to T, crossing off the original numbers and replacing them with the capacity left. Add to the back flow what has been taken away from the forward flow.
3. Add back flow to the minimum amount sent through to find the actual (maximum) flow