Training program 1 has the cricket team starting from exercise station `S` and running to exercise station `O`.

For safety reasons, the cricket coach has placed a restriction on the maximum number of people who can use the tracks in the fitness park.

The directed graph below shows the capacity of the tracks, in number of people per minute.
 

1. How many different routes from `S` to `O` are possible?   (1 mark)

When considering the possible flow of people through this network, many different cuts can be made.

2. Determine the capacity of Cut 1, shown above.  (1 mark)
   
3. What is the maximum flow from `S` to `O`, in number of people per minute?  (1 mark)

A museum is planning an exhibition using five rooms.

The museum manager draws a network to help plan the exhibition. The vertices `A`, `B`, `C`, `D` and `E` represent the five rooms. The number on the edges represent the maximum number of people per hour who can pass through the security checkpoints between the rooms.
 

1. What is the capacity of the cut shown?  (1 mark)
2. The museum manager is planning for a maximum of 240 visitors to pass through the exhibition each hour. By using the 'minimum cut-maximum flow' theorem, the manager determines that the plan does not provide sufficient flow capacity.
   

    

   Draw the minimum cut onto the network below and recommend a change that the manager could make to one or more security checkpoints to increase the flow capacity to 240 visitors per hour.   (2 marks)
    
      
   

The graph below shows the possible number of postal deliveries each day between the Central Mail Depot and the Zenith Post Office.

The unmarked vertices represent other depots in the region.

The weighting of each edge represents the maximum number of deliveries that can be made each day.
 

1.  Cut A, shown on the graph, has a capacity of 10.
   

    

    Two other cuts are labelled as Cut B and Cut C.

   1.  Write down the capacity of Cut B.  (1 mark)
   2.  Write down the capacity of Cut C. (1 mark)
2.  Determine the maximum number of deliveries that can be made each day from the Central Mail   Depot to the Zenith Post Office.  (1 mark)

In the network below, the values on the edges give the maximum flow possible between each pair of vertices. The arrows show the direction of flow. A cut that separates the source from the sink in the network is also shown.
 

 
Part 1

The capacity of this cut is

A.   `14`

B.   `18`

C.   `23`

D.   `31`

E.   `40`

Part 2

A.    `7`

B.   `10`

C.   `11`

D.   `12`

E.   `20`

As an attraction for young children, a miniature railway runs throughout the new housing estate.

The trains travel through stations that are represented by nodes on the directed network diagram below.

The number of seats available for children, between each pair of stations, is indicated beside the corresponding edge.
 

 
Cut 1, through the network, is shown in the diagram above.

1. Determine the capacity of Cut 1.  (1 mark)
2. Determine the maximum number of seats available for children for a journey that begins at the West Terminal and ends at the East Terminal.  (1 mark)

On one particular train, 10 children set out from the West Terminal.

No new passengers board the train on the journey to the East Terminal.

3. Determine the maximum number of children who can arrive at the East Terminal on this train.  (1 mark)

The rangers at the wildlife park restrict access to the walking tracks through areas where the animals breed.

The edges on the directed network diagram below represent one-way tracks through the breeding areas. The direction of travel on each track is shown by an arrow. The numbers on the edges indicate the maximum number of people who are permitted to walk along each track each day.
 

1. Starting at `A`, how many people, in total, are permitted to walk to `D` each day?  (1 mark)

One day, all the available walking tracks will be used by students on a school excursion.

The students will start at `A` and walk in four separate groups to `D`.

Students must remain in the same groups throughout the walk.

2. 1. Group 1 will have 17 students. This is the maximum group size that can walk together from `A` to `D`.
      

       

      Write down the path that group 1 will take.  (1 mark)

   2. Groups 2, 3 and 4 will each take different paths from `A` to `D`.
      

       

      Complete the six missing entries shaded in the table below.  (2 marks)