SmarterEd

Aussie Maths & Science Teachers: Save your time with SmarterEd

Networks, STD2 N3 2024 GEN2 14

A manufacturer makes deliveries to the supermarket via a number of storage warehouses, and . These eight locations are represented as vertices in the network below.

The numbers on the edges represent the maximum number of deliveries that can be made between these locations each day.
 

  1. When considering the possible flow of deliveries through this network, many different cuts can be made.   
  2. Determine the capacity of Cut 1, shown above.   (1 mark)

  3. Determine the maximum number of deliveries that can be made each day from the manufacturer to the supermarket.   (2 marks)

    

Show Answers Only

a.    

b.    

Show Worked Solution

a.    


 

b.  

♦ Mean mark (b) 29%.

Networks, STD2 N3 2023 HSC 14 MC

A network with source and sink is shown. The capacities of two paths are labelled. The cut shown on the diagram has a capacity of 30 .
 

Which of the following statements is correct?

  1. The maximum flow is 30.
  2. The maximum flow is 35.
  3. The maximum flow is 30 or less.
  4. The maximum flow is 30 or more.
Show Answers Only

Show Worked Solution

♦♦ Mean mark 33%.

Networks, STD2 N3 2022 HSC 31

A wildlife park has 5 main attractions connected by directional paths. A simple network is drawn to represent the flow through the park's paths. The number of visitors who can access each path at any one time is also shown.
 

   

  1. What is the flow capacity of the cut shown?  (1 mark)

  2. By showing a suitable cut on the diagram below, explain why the network's current maximum flow capacity is less than 40 visitors.  (2 marks)
     

  3. One path is to be increased in capacity so that the overall maximum flow will be 40 visitors at any one time.
  4. Which path could be increased and by how much?  (2 marks)

Show Answers Only
  2.  
     
Show Worked Solution

a.   


 

b.  
       

 
   


♦ Mean mark part (a) 45%.
♦♦ Mean mark part (b) 33%.

 

c.   

 


Mean mark 52%.

Networks, STD2 N3 FUR2 4

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

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. Determine the capacity of Cut 1, shown above.  (1 mark)

  2. What is the maximum flow from to , in number of people per minute?  (1 mark)

Show Answers Only
Show Worked Solution
a.  
   

 

b.   

♦♦ Mean mark part (c) 32%.


 

Networks, STD2 N3 2019 HSC 40

A museum is planning an exhibition using five rooms.

The museum manager draws a network to help plan the exhibition. The vertices , , , and 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)
     
       

Show Answers Only
  2.   

Show Worked Solution
a.   
   

♦♦ Mean mark 32%.
COMMENT: In part (a), edge BC flows from the exit to the entry and is therefore not counted.

b.   

 

♦♦♦ Mean mark 19%.
COMMENT: In part (b), edge BC now flows from entry to exit in the new “minimum” cut and is counted.

Networks, STD2 N3 SM-Bank 45

An oil pipeline network is drawn below that shows the flow capacity of oil pipelines in kilolitres per hour.
 


 

A cut is shown.

  1. What is the capacity of the cut.  (1 mark)

  2. Calculate the minimum cut of this network?  (2 marks)

  3. Copy the network diagram, showing the maximum flow capacity of the network by labelling the flow of each edge.  (2 marks)

Show Answers Only
  3.  
Show Worked Solution
i.   
   

 

ii. 

♦♦ COMMENT: Be very careful! RS is not included as it goes from sink to source.
 


  

 

 

iii.   

Networks, STD2 N3 2018 FUR2 1

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)

Show Answers Only
  2.  
Show Worked Solution
a.i.   
   

 

a.ii.   
   

♦ Mean mark part (b) 32%.
COMMENT: Review carefully! Most common incorrect answer was 9.

 

b.  

Networks, STD2 N3 SM-Bank 36

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.
 

vcaa-networks-fur1-2010-6-7

 

  1. Calculate the capacity of the cut shown in the diagram.  (1 mark)

  2. Calculate the maximum flow between source and sink.  (2 marks)

Show Answers Only
Show Worked Solution

i.   

♦ Mean mark part (a) 50%.
COMMENT: A quarter of students incorrectly included the “8” which is flowing in the opposite direction.

 

ii.

vcaa-networks-fur1-2010-6-7i

♦♦ Mean mark part (b) 24%.