10.1. Bandwidth Allocation Problem

Try these first

1. 1.

   What does the term 'network flow' refer to?

   Hint

   Think about how water moves through pipes.

2. 2.

   State one condition of conservation of flow.

   Hint

   Consider what happens at an intersection.

3. 3.

   What is the purpose of the Ford-Fulkerson algorithm?

   • To minimize flow
   • To compute maximum flow
   • To calculate min cut

   Hint

   Think about the algorithm's primary objective.

4. 4.

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

   • True
   • False

   Hint

   Consider what a cut represents in the flow context.

5. 5.

   Given a directed graph with specified capacities, use the Ford-Fulkerson algorithm to calculate the maximum flow from the source to the sink and document each step of flow augmentation.

   Hint

   Sketch the graph and track changes in each iteration for better visualization.

6. 6.

   Create a network example demonstrating the max flow min cut theorem by calculating the maximum flow and showing the minimum cut.

   Hint

   Visualize cuts in the graph to understand how they restrict flow.