SmarterEd

Aussie Maths & Science Teachers: Save your time with SmarterEd

Networks, STD2 N3 2024 NHT 38*

The following directed graph represents the one-way paths between attractions at an historical site. The entrance, exit and attractions are represented by vertices.

The numbers on the edges represent the maximum number of visitors allowed along each path per hour.
 

Determine the maximum number of visitors able to walk from the entrance to the exit each hour?   (3 marks)

Show Answers Only

\(\text{Maximum number = 76}\)

Show Worked Solution

\(\text{Max flow = min cut}\)

\(\text{Discounting flows that move from “exit” to “entrance”:}\)

\(\text{Max flow}\ = 13+16+9+17+21 = 76\ \text{visitors}\)

Networks, STD2 N3 2024 GEN2 14

A manufacturer \((M)\) makes deliveries to the supermarket \((S)\) via a number of storage warehouses, \(L, N, O, P, Q\) and \(R\). 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.    \(46\)

b.    \(37\)

Show Worked Solution

a.    \(13+18+6+9=46\)

\(\text{(Reverse flow}\ Q → O\ \text{is not counted.)}\)
 

b.  

\(\text{Max deliveries (min cut)}\ =13+5+11+8=37\)

♦ Mean mark (b) 29%.

Networks, STD2 N3 SM-Bank 24

The network below shows the one-way paths between the entrance, \(A\), and the exit, \(H\), 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.

The minimum cut of the network is drawn, showing the maximum flow capacity of the maze is 23 children per minute.
 

One path in the maze is to be changed.

Determine the changes in the maximum flow capacity of the network in each of the following changes

  1. the capacity of flow along the edge \(GH\) is increased to 16.   (1 mark)

  2. the capacity of flow along the edge \(C E\) is increased to 12.   (2 marks)

  3. the direction of flow along the edge \(G F\) is reversed.   (2 marks)

Show Answers Only

i.    \(GH ↑ 16,\ \text{minimum cut = 27}\)

\(\text{Change: increases by 4}\)

ii.    \(CE ↑ 12,\ \text{minimum cut = 24}\)

\(\text{Change: increases by 1}\)

iii.   \(GF\ \text{is reversed, minimum cut = 30 (close to exit H)}\)

\(\text{Change: increases by 7}\)

Show Worked Solution

i.    \(GH ↑ 16,\ \text{minimum cut = 27}\)
 

\(\text{Change: increases by 4}\)
 

ii.    \(CE ↑ 12,\ \text{minimum cut = 24}\)
 

\(\text{Change: increases by 1}\)
 

iii.   \(GF\ \text{is reversed, minimum cut = 30 (close to exit H)}\)
 

\(\text{Change: increases by 7}\)

Networks, STD2 N3 SM-Bank 22

The network below shows the one-way paths between the entrance, \(A\), and the exit, \(H\), 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.
 

Cuts on this network are used to consider the possible flow of children through the maze.

Determine the capacity of the minimum cut of this network.   (2 marks)

Show Answers Only

\(\text{Minimum cut = 23} \)

Show Worked Solution

\(\text{Minimum cut}\ = 12+4+7 = 23\)

Networks, STD2 N3 2022 HSC 31

A wildlife park has 5 main attractions `(A, B, C, D, E)` 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
  1. `40`
  2.  
     
  3. `text{Max flow = min cut = 35}`
  4. `AE\ text{or}\ DE\ text{could be increased by 5}`
Show Worked Solution

a.   `text{Flow capacity = 10 + 20 + 10 = 40}`

`text{(DE is not counted as it runs from sink → source)}`
 

b.  
       

`text{Min Cut = Max Flow}`

`text{Max Flow}` `=15+10+10`  
  `=35<40`  


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

 

c.   `text{Two strategies:}`

  • `AE\ text{could be increased by 5}`
  • `DE\ text{could be increased by 5}`

`text{(both strategies would increase the minimum cut to}`

  `text{40 by increasing the flow to vertex}\ E\ text{to 30)}`


Mean mark 52%.

Networks, STD2 N3 FUR2 4

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

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

Show Answers Only
  1. `52`
  2. `50`
Show Worked Solution
a.   `text{Capacity (Cut 1)}` `= 20 + 12 + 20`
    `= 52`

 

b.   `text(Max flow/minimum cut)`

♦♦ Mean mark part (c) 32%.

`= 20 + 10 + 20`

`= 50`
 

Networks, STD2 N3 2020 HSC 30

The network diagram shows a series of water channels and ponds in a garden. The vertices `A`, `B`, `C`, `D`, `E`,  and `F` represent six ponds. The edges represent the water channels which connect the ponds. The numbers on the edges indicate the maximum capacity of the channels.
 


 

  1. Determine the maximum flow of the network.   (2 marks)

  2. A cut is added to the network, as shown.
     
       
    Is the cut shown a minimum cut? Give a reason for your answer.  (1 mark)

Show Answers Only
  1. `275`
  2. `text{Show Worked Solutions}`
Show Worked Solution

a.   `text(By trial and error, find min cut/max flow:)`

♦ Mean mark 41%.

 

  `text{Maximum Flow}` `= 50 + 75 + 100 +50`
    `= 275`

♦♦ Mean mark 28%.
b.      `text{Capacity of the cut}` `= 50 + 75 + 200`
    `= 325`

 
`therefore \ text{It is not a minimum cut (the cut in part (a) = 275 < 325)} `

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 `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)
     
       

Show Answers Only
  1. `290`
  2.   

Show Worked Solution
a.    `text(Capacity)` `= 130 + 90 + 70`
    `= 290`

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

b.   `text(Maximum flow capacity:)`

 

`text(Minimum cut = 80 + 40 + 65 + 45 = 230)`

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

`text(If security is improved to increase the flow)`

`text(between Room C and Room B by 10 visitors)`

`text(per hour, the network’s flow capacity increases)`

`text(to 240.)`

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
  1. `35`
  2. `text(See Worked Solutions)`
  3.  
Show Worked Solution
i.    `text(Capacity of cut)` `= 7 + 15 + 13`
    `= 35\ text(kL/h)`

 

ii. 

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


  

`text(Minimum cut)` `= 7 + 14 + 9`
  `= 30\ text(kL/h)`

 

iii.   

Networks, STD2 N3 SM-Bank 46

A network diagram is drawn below.
 

 
 

  1. Calculate the maximum flow through this network.  (2 marks)

  2. Copy the network above and illustrate the maximum flow capacity.  (2 marks)

Show Answers Only
  1. `28`
  2.  
Show Worked Solution
i.   

 

`text(Maximum flow)` `=\ text(minimum cut)`
  `= 8 + 8 + 7 + 5`
  `= 28`

 

ii.   

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
    1. `9`
    2. `13`
  2.  `7`
Show Worked Solution
a.i.    `text{Capacity (Cut B)}` `= 3 + 2 + 4`
    `= 9`

 

a.ii.    `text{Capacity (Cut C)}` `= 3 + 6 + 4`
    `= 13`

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

 

b.  `text(Minimum cut) = 2 + 2 + 3 = 7`

`:.\ text(Maximum deliveries) = 7`

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
  1. `23`
  2. `10`
Show Worked Solution

i.   `text(Capacity of the cut)`

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

`= 11 + 5 + 7`

`= 23`

 

ii.

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

`text(The maximum flow)`

♦♦ Mean mark part (b) 24%.

`=\ text{minimum cut (see above)}`

`= 4 + 2 + 3 + 1`

`= 10`

Networks, STD2 N3 SM-Bank 35

The following directed graph shows the flow of water, in litres per minute, in a system of pipes connecting the source to the sink.
 

 
Calculate the maximum flow, in litres per minute, from the source to the sink.  (2 marks)

Show Answers Only

`18`

Show Worked Solution
`text(Maximum Flow)` `=\ text(Capacity of Minimum Cut)`
  `= 2 + 10 + 6`
  `= 18\ \ text(litres/minute)`

Networks, STD2 N3 SM-Bank 34

The arrows on the diagram below show the direction of the flow of waste through a series of pipelines from a factory to a waste dump.

The numbers along the edges show the number of megalitres of waste per week that can flow through each section of pipeline.
 

NETWORKS, FUR1 2015 VCAA 4 MC

 
The minimum cut is shown as a dotted line.

Calculate the capacity of this cut, in megalitres of waste per week.  (2 marks)

Show Answers Only

`26`

Show Worked Solution

`text(Flows from the waste dump side of the minimum cut to)`

`text(the factory side are ignored.)`
 

`:.\ text{Minimum Cut}`

`= 5 + 2 + 12 + 7`

`= 26\ \ text(ML/week)`