SmarterEd

Aussie Maths & Science Teachers: Save your time with SmarterEd

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 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 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 17

The network diagram represents a system of roads connecting a shopping centre to the motorway.

Two routes from the shopping centre connect to A and one route connects D to F.

The number on the edge of each road indicates the number of vehicles that can travel on it per hour.
 


 

Draw additional road(s) on the diagram to maximise the capacity. Include the number of vehicles that can travel on each road.  (2 marks)

Show Answers Only

`text(Solutions could be:)`

Show Worked Solution

`text(Two possible solutions are:)`

`text(Note that the added roads above make the minimum cut/max)`

`text(flow increase to 170 vehicles per hour.)`

Networks, STD2 N3 SM-Bank 16 MC

The network diagram represents a system of roads connecting a shopping centre to the motorway.

Two routes from the shopping centre connect to A and one route connects to D to F.

The number on the edge of each road indicates the number of vehicles that can travel on it per hour.

At present, the capacity of the network from the shopping centre to the motorway is not maximised.

Which additional road(s) would increase the network capacity to its maximum?

A. A road from A to F with a capacity of 20 vehicles per hour
B. A road from B to E with a capacity of 30 vehicles per hour
C. A road from C to F with a capacity of 30 vehicles per hour and a road from E to F with a capacity of 60 vehicles per hour
D. A road from B to F with a capacity of 30 vehicles per hour and a road from D to F with a capacity of 30 vehicles per hour
Show Answers Only

`text(D)`

Show Worked Solution

`text(Consider option D:)`

`text(Adding these two roads increases the minimum cut/maximum)`

`text(flow to 170 vehicles per hour throughout the network.)`

`=>\ text(D)`