SmarterEd

Aussie Maths & Science Teachers: Save your time with SmarterEd

Networks, STD2 N3 2023 HSC 14 MC

A network with source `A` and sink `B` 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

`C`

Show Worked Solution

`text{The cut shows a maximum flow of 30, however there is no information}`

`text{that it is the minimum cut across the network}`

`text{(i.e. it is possible the minimum cut is lower than 30).}`

`=>C`

♦♦ Mean mark 33%.

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 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 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 2008 FUR1 6 MC

networks-fur1-2008-vcaa-6-mc

 
For the graph above, the capacity of the cut shown is

A.   `36`

B.   `30`

C.   `42`

D.   `46`

Show Answers Only

`=> C`

Show Worked Solution

`text(Ignoring any flows that cross the cut from the)`

♦♦ Mean mark 35%.
MARKER’S COMMENT: For an individual flow to contribute to the “cut”, it must flow from the source to the sink.

`text(sink side to the source side.)`
 

`text(Capacity of the cut)`

`= 4 + 2 + 7 + 9 + 8 + 6 + 6`

`= 42`

`=> C`

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`