10.4. Setting Up Linear Program

Try these first

1. 1.

   What is the source in a network flow?

   Hint

   Think about where the flow begins.

2. 2.

   What does the term 'sink' refer to?

   Hint

   Consider where the flow is headed.

3. 3.

   What is the purpose of the Ford-Fulkerson algorithm?

   • To minimize flow in a network
   • To compute the maximum flow in a network
   • To disconnect the source and sink

   Hint

   Consider what the algorithm aims to achieve.

4. 4.

   True or False: The maximum flow in a network can exceed the minimum cut capacity.

   • True
   • False

   Hint

   Reflect on the relationship between flow and capacity constraints.

5. 5.

   Given a directed graph with edges having specific capacities, use the Ford-Fulkerson algorithm to calculate the maximum flow from source 's' to sink 't'. Demonstrate all steps including residual graph representations.

   Hint

   Start at zero flow and find paths iteratively.

6. 6.

   Prove the Max Flow-Min Cut Theorem by considering a specific network and demonstrating that the maximum flow equals the smallest cut capacity.

   Hint

   Experiment with identifying cuts in a sample network.