Network Flow

In network graphs where there is a flow, the start is known as the source (where all the outdegrees are) and the finish is known as the sink (where all the indegrees are).

As a general rule the source is generally located on the left hand side or top, and the sink is generally on the right hand side or the bottom of the graph.

VCAA 2013 Further Mathematics Exam 2 Question 3 p.36

Maximum Flow

The maximum flow is the largest number of ‘flow’ that can be achieved on the network graph.

One method of finding the maximum flow is to find a cut with the minimum capacity.

NOTE: The capacity of a cut is the sum of the capacities of the edges that are crossed by the cut.

Essential Further Mathematics 4ed 2012 (Figure 24.4)

C1 = 7

C2 = 1

C3 = 8

C4 = 8

The maximum flow for this graph is 7 given by cut C1.

NOTE: When counting the edges towards the total of your cut, you must ensure that the edges flow from the source to the sink NOT sink to source. i.e. the arrow must point to the overall sink.

In the above example, the edge BA was not counted in the cut C2 because its arrow is not pointing towards the sink (D).

Essential Further Mathematics 4ed 2012 (Example 6 p.649)

In this example, the edge DC in cut C4 in NOT counted because it is against the flow from source to sink.

The maximum flow of the graph is 25 given by cut C5.