10. Network Flows

Try these first

1. 1.

   What is meant by the term 'network flow'?

   Hint

   Think about the flow of materials like water or oil.

2. 2.

   Define conservation of flow.

   Hint

   What happens to flow in a circle?

3. 3.

   What is the purpose of the Ford-Fulkerson algorithm?

   • To determine the shortest path
   • To calculate maximum flow
   • To find the least cost

   Hint

   What is the main goal of the required analysis?

4. 4.

   True or False: The maximum flow in a network can exceed the capacity of the edges.

   • True
   • False

   Hint

   Think about the limits placed on each edge.

5. 5.

   Given a directed graph with specified capacities and an initial flow, calculate the maximum flow using the Ford-Fulkerson algorithm. Show your working steps.

   Hint

   Identify paths systematically and document capacity updates.

6. 6.

   Create a flow network diagram with a source, sink, and nodes with varying capacities. Identify the maximum flow and cut based on the given diagram.

   Hint

   Make sure to check edge capacities thoroughly to find the minimum cut.