SmarterEd

Aussie Maths & Science Teachers: Save your time with SmarterEd

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

b.    \(37\)

c.    \(\text{R and S}\)

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%.

 
c.   \(\text{The number of deliveries should be increased between}\)

\(\text{locations R and S.}\)

♦ Mean mark (c) 22%.

Networks, GEN1 2023 VCAA 39-40 MC

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.
 

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 \(C E\) to 12
  2. increasing the capacity of flow along the edge \(FH\) to 14
  3. increasing the capacity of flow along the edge \(GH\) to 16
  4. reversing the direction of flow along the edge \(C F\)
  5. reversing the direction of flow along the edge \(G F\)
Show Answers Only

\(\text{Question 39:}\ B \)

\(\text{Question 40:}\ E \)

Show Worked Solution

\(\text{Question 39} \)

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

\(\Rightarrow B\)
 

\(\text{Question 40}\)

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

\(FH ↑ 14,\ \text{minimum cut = 23}\)

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

\(CF\ \text{is reversed, minimum cut = 29}\)

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

\(\Rightarrow E\)