10.8. Choosing Paths in Ford-Fulkerson

Try these first

1. 1.

   Define flow in the context of network theory.

   Hint

   Think about what is being transferred from the source to the sink.

2. 2.

   What does capacity refer to in a network?

   Hint

   Consider the limits on how much can pass through a pipe.

3. 3.

   What is the primary goal of the Ford-Fulkerson algorithm?

   • To minimize the flow
   • To maximize the flow
   • To eliminate edges

   Hint

   Think about the algorithm’s purpose in a network flow context.

4. 4.

   True or False: The maximum flow is always less than or equal to the minimum cut.

   • True
   • False

   Hint

   Consider how cutting edges affects the flow capacity.

5. 5.

   Given a directed graph with specific edge capacities, use the Ford-Fulkerson algorithm to determine the maximum flow.

   Hint

   Keep track of the residual graph as you progress through augmentations.

6. 6.

   Explain how changing the capacity of an edge affects the maximum flow. Provide at least two scenarios.

   Hint

   Think about what happens to flow when key paths change.