SmarterEd

Aussie Maths & Science Teachers: Save your time with SmarterEd

Networks, GEN2 2024 VCAA 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.   (1 mark)

  4. The manufacturer wants to increase the number of deliveries to the supermarket.
  5. This can be achieved by increasing the number of deliveries between one pair of locations.
  6. Complete the following sentence by writing the locations on the lines provided:
  7. To maximise this increase, the number of deliveries should be increased between
    locations ____ and  ____.       (1 mark)

    

Show Answers Only

a.    

b.    

c.    

Show Worked Solution

a.    


 

b.  

♦ Mean mark (b) 29%.

 
c.   

♦ Mean mark (c) 22%.

Networks, GEN1 2023 VCAA 39-40 MC

The network below shows the one-way paths between the entrance, , and the exit, , of a children's maze.

The vertices represent the intersections of the one-way paths.

The number on each edge is the maximum number of children who are allowed to travel along that path per minute.
 

Question 39

Cuts on this network are used to consider the possible flow of children through the maze. The capacity of the minimum cut would be

  1. 20
  2. 23
  3. 24
  4. 29
  5. 30

 
Question 40

One path in the maze is to be changed.

Which one of these five changes would lead to the largest increase in flow from entrance to exit?

  1. increasing the capacity of flow along the edge to 12
  2. increasing the capacity of flow along the edge to 14
  3. increasing the capacity of flow along the edge to 16
  4. reversing the direction of flow along the edge
  5. reversing the direction of flow along the edge
Show Answers Only

Show Worked Solution


 

NETWORKS, FUR2 2021 VCAA 3

The network diagram below shows the local road network of Town .

The number on the edges indicate the maximum number of vehicles per hour that can travel along each road in this network.

The arrows represent the permitted direction of travel.

The vertices and represent the intersections of the roads.
 

  1. Determine the maximum number of vehicles that can travel from the entrance to the exit per hour.   (1 mark)

  2. The local council plans to increase the number of vehicles per hour that can travel from the entrance to the exit by increasing the capacity of only one road.
  3.  i. Complete the following sentence by filling in the boxes provided.   (1 mark)

        The road that should have its capacity increased is the road from vertex  
     
    		  to 
     
  4. ii. What should be the minimum capacity of this road to maximise the flow of vehicles from the entrance to the exit?   (1 mark)

Show Answers Only
  2.  i.
  3. ii.
Show Worked Solution

a.     

 

 

 

b.i. 


 

b.ii.

 
 


 

NETWORKS, FUR2 2020 VCAA 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. How many different routes from to are possible?   (1 mark)

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

  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.  
   

♦♦ Mean mark part (a) 30%.

 

 

b.  
   

 

c.   

♦♦ Mean mark part (c) 32%.


 

NETWORKS, FUR1 2020 VCAA 9 MC

The flow of liquid through a series of pipelines, in litres per minute, is shown in the directed network below.
 


 

Five cuts labelled A to E are shown on the network.

The number of these cuts with a capacity equal to the maximum flow of liquid from the source to the sink, in litres per minute, is

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
Show Answers Only

Show Worked Solution

NETWORKS, FUR1 2019 STD2 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, FUR2 2018 VCAA 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.
     i.  Write down the capacity of Cut B.   (1 mark)

    ii.  Write down the capacity of Cut C.   (1 mark)

  1. 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
  1.  i. 
    ii.  
  2.  
Show Worked Solution
a.i.   
   

 

a.ii.   
   

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

 

b.  

NETWORKS, FUR1 2017 VCAA 8 MC

The flow of oil through a series of pipelines, in litres per minute, is shown in the network below.
 

 
The weightings of three of the edges are labelled .

Five cuts labelled A–E are shown on the network.

The maximum flow of oil from the source to the sink, in litres per minute, is given by the capacity of

Show Answers Only

Show Worked Solution

NETWORKS, FUR1 2010 VCAA 6-7 MC

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

 
Part 1

The capacity of this cut is

A.   

B.   

C.   

D.   

E.   

 

Part 2

The maximum flow between source and sink through the network is

A.   

B.   

C.   

D.   

E.   

Show Answers Only

Show Worked Solution

Part 1

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

 

Part 2

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

♦♦♦ Mean mark 24%.

NETWORKS, FUR1 2012 VCAA 7 MC

Vehicles from a town can drive onto a freeway along a network of one-way and two-way roads, as shown in the network diagram below.

The numbers indicate the maximum number of vehicles per hour that can travel along each road in this network. The arrows represent the permitted direction of travel.

One of the four dotted lines shown on the diagram is the minimum cut for this network.
  

networks-fur1-2012-vcaa-7-mc-1

 
The maximum number of vehicles per hour that can travel through this network from the town onto the freeway is

A.  

B. 

C. 

D. 

E. 

Show Answers Only

Show Worked Solution

♦♦♦ Mean mark 23%.

NETWORKS, FUR2 2007 VCAA 3

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.
 

NETWORKS, FUR2 2007 VCAA 3

 
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.

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

Show Answers Only
Show Worked Solution

a.  

♦♦ Mean mark for all parts (combined) was 33%.
MARKER’S COMMENT: A common error was counting the edge with “10” in the reverse direction (it should be ignored).

 

b.    networks-fur2-2007-vcaa-3-answer
 
 

 

c.  


  

NETWORKS, FUR1 2014 VCAA 9 MC

A network of tracks connects two car parks in a festival venue to the exit, as shown in the directed graph below.
 

 
The arrows show the direction that cars can travel along each of the tracks and the numbers show each track’s capacity in cars per minute.

Five cuts are drawn on the diagram.

The maximum number of cars per minute that will reach the exit is given by the capacity of

A.  Cut A

B.  Cut B

C.  Cut C

D.  Cut D

E.  Cut E

Show Answers Only

Show Worked Solution

♦♦♦ Mean mark 24%.
COMMENT: Note that the “4” is not included in Cut D as it is flowing in the opposite direction.

NETWORKS, FUR2 2013 VCAA 3

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.
 

NETWORKS, FUR2 2013 VCAA 31
 

  1. Starting at , how many people, in total, are permitted to walk to 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 and walk in four separate groups to .

Students must remain in the same groups throughout the walk.

  1. i. Group 1 will have 17 students. This is the maximum group size that can walk together from to .
    Write down the path that group 1 will take.  (1 mark)

  2. ii. Groups 2, 3 and 4 will each take different paths from to .
    Complete the six missing entries shaded in the table below.   (2 marks)

NETWORKS, FUR2 2013 VCAA 32

Show Answers Only
    2.  
       
      Networks, FUR2 2013 VCAA 3_2 Answer1
Show Worked Solution
a.   
   
   
♦ Mean mark of all parts (combined) was 41%.

 


  

b.i.   
  

b.ii.   

 

 

Networks, FUR2 2013 VCAA 3_2 Answer1

NETWORKS, FUR2 2011 VCAA 4

Stormwater enters a network of pipes at either Dunlop North (Source 1) or Dunlop South (Source 2) and flows into the ocean at either Outlet 1 or Outlet 2.

On the network diagram below, the pipes are represented by straight lines with arrows that indicate the direction of the flow of water. Water cannot flow through a pipe in the opposite direction.

The numbers next to the arrows represent the maximum rate, in kilolitres per minute, at which stormwater can flow through each pipe.

 

NETWORKS, FUR2 2011 VCAA 4_1
 

  1. Complete the following sentence for this network of pipes by writing either the number 1 or 2 in each box.  (1 mark)

NETWORKS, FUR2 2011 VCAA 4_2

  1. Determine the maximum rate, in kilolitres per minute, that water can flow from these pipes into the ocean at Outlet 1 and Outlet 2.  (2 marks)

A length of pipe, show in bold on the network diagram below, has been damaged and will be replaced with a larger pipe.

 

NETWORKS, FUR2 2011 VCAA 4_3
 

  1. The new pipe must enable the greatest possible rate of flow of stormwater into the ocean from Outlet 2.
  2. What minimum rate of flow through the pipe, in kilolitres per minute, will achieve this?  (1 mark)

Show Answers Only


Show Worked Solution

a.  

♦ Mean mark of all parts (combined) was 35%.

 

b.    NETWORKS, FUR2 2011 VCAA 4 Answer

 

 

c.