10.7. Max Flow Min Cut Theorem

Try these first

1. 1.

   Define a flow network.

   Hint

   Think about how flow is managed in a system.

2. 2.

   What is the principle of conservation of flow?

   Hint

   Reflect on the balance of flow in a network.

3. 3.

   What must be true about a flow in a flow network?

   • It can exceed edge capacities
   • Inflow equals outflow at nodes
   • It can accumulate at nodes

   Hint

   Consider how flow behaves at nodes in a network.

4. 4.

   The Ford-Fulkerson algorithm aims to compute what?

   • True
   • False

   Hint

   Reflect on the purpose of the algorithm.

5. 5.

   Given the flow network with the following capacities: A-B (10), B-C (5), A-C (15), C-D (10), and B-D (15). Calculate the maximum flow from A to D.

   Hint

   Try breaking the problem down into smaller flows and add them iteratively.

6. 6.

   Explain how varying capacities on edges of a network impact the maximum flow and the minimum cut using a constructed graph.

   Hint

   Build scenarios revealing how different capacities influence flow dynamics.