networks3

Maximum Flow and Minimum Cut Problem

During peak traffic hours, many cars are travelling from a downtown parkade to the nearest freeway on-ramp.  The traffic engineers have decided to widen some downtown roads to accommodate the heavy flow of cars traveling between these two points.  Which roads should the engineers widen in order to achieve this goal?

The video shows a network of roads that connect the parkade (at node A) to the freeway on-ramp (at node G).  The answer to the question is found by first finding the maximum flow from A to G, and then analyzing the flow pattern to find the minimum cut. Arcs in the minimum cut set are restricting the flow between A and G.

Arc labelling: Arcs are labelled with their flow capacities in either direction. The figure below shows the arc connecting nodes A and B. This shows that the arc has a flow capacity of 5 in the A-to-B direction, and a flow capacity of 0 in the B-to-A direction, in other words it is a one-way street from A to B.