Aussie Maths & Science Teachers: Save your time with SmarterEd
The network below shows the flow of water, in litres per minute, in a system of pipes connecting the source to the sink.
Part 1
What is the capacity of Cut 1?
Part 2
What is the maximum flow of water, in litres per minute, from source to sink?
\(\text{Part 1}\)
\(\text{Capacity (Cut 1)}=12+5+3+7=27\)
\(\Rightarrow A\)
\(\text{Part 2}\)
\(\text{Minimum Cut}=6+4+7=17\)
\(\Rightarrow B\)
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.
Question 38
What is the maximum number of visitors able to walk from the entrance to the exit each hour?
Question 39
A group of students set out from the entrance and walk to the exit. The students all walk together and travel along the same route. They are the only people visiting the site that hour. What is the maximum number of students that could be in the group?
\(\text{Question 38}\)
\(\text{Max flow = min cut}\)
\(\text{Max flow = 13+16+9+17+21=76\)
\(\Rightarrow B\)
\(\text{Question 39}\)
\(\text{Given all students must take the same route:}\)
\(\text{Path for max students is 32 → 20 → 32 → 21}\)
\(\text{Max students = minimum capacity of any edge = 20}\)
\(\Rightarrow D\)
The vertices of the graph below represent cabins in a holiday park, and the water pump \((P)\) that will supply them. The numbers on the edges show the length, in metres, of water pipe required to connect the cabins and the pump.
The water pipes will cost $52 per metre. What is the minimum cost to link all the cabins to the water pump \((P)\) ?
Minimum spanning tree:
\(\text{MST}\ =8+9+11+8+9+9+7+12=73\)
\(\therefore\ \text{Minimum cost}\ = 73 \times 52=\$3796\)
\(\Rightarrow B\)
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 WORK AREA LINES (style=lined) --- --- 1 WORK AREA LINES (style=lined) --- --- 0 WORK AREA LINES (style=lined) ---
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\) \(\text{locations R and S.}\)
locations ____ and ____. (1 mark)
Show Worked Solution
♦ Mean mark (b) 29%.
c. \(\text{The number of deliveries should be increased between}\)
♦ Mean mark (c) 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.
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
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?
\(\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\)
The network diagram below shows the local road network of Town `M`.
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 `A, B, C, D, E` and `F` represent the intersections of the roads.
--- 1 WORK AREA LINES (style=lined) ---
--- 0 WORK AREA LINES (style=lined) ---
| The road that should have its capacity increased is the road from vertex |
|
to |
|
--- 5 WORK AREA LINES (style=lined) ---
a.
| `text{Minimum cut}` | `= 680 + 650` |
| `= 1330` |
`:. \ text{Maximum number of vehicles} = 1330`
b.i. `text{Vehicles from} \ A \ text{to} \ B \ text{restricted to 700 per hour.}`
`:. \ text{Road to increase capacity is from} \ A \ text{to} \ D.`
b.ii. `text{Minimum cut} = 1330 \ text{(partial)}`
`text{Next lowest cut} = 620 + 840 = 1460`
`text{Extra capacity} = 1460 – 1330 = 130`
`:. \ text{Minimum capacity of road} \ A \ text{to}\ D \ text{should be}`
`= 650 + 130`
`= 780`
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.
--- 2 WORK AREA LINES (style=lined) ---
When considering the possible flow of people through this network, many different cuts can be made.
--- 2 WORK AREA LINES (style=lined) ---
--- 3 WORK AREA LINES (style=lined) ---
| a. | `text(Routes: )` | `SMO, STUNO, STUVO, STUVPO, SRQUNO,SRQUVO,` |
| `SRQUVPO, SRQVO, SRQVPO, SRQPO` |
`:. 10\ text(routes)`
| b. | `text{Capacity (Cut 1)}` | `= 20 + 12 + 20` |
| `= 52` |
c. `text(Max flow/minimum cut)`
`= 20 + 10 + 20`
`= 50`
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
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.
--- 2 WORK AREA LINES (style=lined) ---
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)
--- 4 WORK AREA LINES (style=lined) ---
| 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.)`
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.
Two other cuts are labelled as Cut B and Cut C.
i. Write down the capacity of Cut B. (1 mark)
--- 2 WORK AREA LINES (style=lined) ---
--- 2 WORK AREA LINES (style=lined) ---
--- 2 WORK AREA LINES (style=lined) ---
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 `x`.
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
The following directed graph shows the flow of water, in litres per minute, in a system of pipes connecting the source to the sink.
The maximum flow, in litres per minute, from the source to the sink is
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.
Part 1
The capacity of this cut is
A. `14`
B. `18`
C. `23`
D. `31`
E. `40`
Part 2
The maximum flow between source and sink through the network is
A. `7`
B. `10`
C. `11`
D. `12`
E. `20`
Part 1
`text(Capacity of the cut)`
`= 11 + 5 + 7`
`= 23`
`=> C`
Part 2
`text(The maximum flow)`
`=\ text{minimum cut (see above)}`
`= 4 + 2 + 3 + 1`
`= 10`
`=> B`
The maximum flow from source to sink through the network shown above is
A. `6`
B. `7`
C. `8`
D. `11`
E. `16`
| `text(Maximum flow)` | `=\ text(minimum cut)` |
| `= 1 + 4 + 2` | |
| `= 7` |
`=> B`
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.
The maximum number of vehicles per hour that can travel through this network from the town onto the freeway is
A. `310`
B. `330`
C. `350`
D. `370`
E. `390`
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.
Cut 1, through the network, is shown in the diagram above.
--- 3 WORK AREA LINES (style=lined) ---
--- 3 WORK AREA LINES (style=lined) ---
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.
--- 5 WORK AREA LINES (style=lined) ---
a. `text(The capacity of Cut 1)`
`=14 + 8 + 13 + 8`
`= 43`
| b. |  |
| `text(Maximum seats)` | `=\ text(minimum cut)` |
| `= 6 + 7 + 9` | |
| `= 22` |
c. `text{The path (edge weights) of the train setting out with}`
`text(10 children starts with: 11 → 13.)`
`text(At the next station, a maximum of 7 seats are available)`
`text(which remain until the East Terminal.)`
`:.\ text(Maximum number of children arriving is 7.)`
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
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.
--- 2 WORK AREA LINES (style=lined) ---
One day, all the available walking tracks will be used by students on a school excursion.
The students will start at `A` and walk in four separate groups to `D`.
Students must remain in the same groups throughout the walk.
--- 1 WORK AREA LINES (style=lined) ---
--- 4 WORK AREA LINES (style=lined) ---
| a. | `text(Maximum flow)` | `=\ text(minimum cut through)\ CD and ED` |
| `= 24 + 13` | ||
| `= 37` |
`:.\ text(A maximum of 37 people can walk)`
`text(to)\ D\ text(from)\ A.`
b.i. `A-B-E-C-D`
b.ii. `text(One solution using the second possible largest)`
`text(group of 11 students and two groups from the)`
`text(remaining 9 students is:)`
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. --- 0 WORK AREA LINES (style=lined) --- --- 5 WORK AREA LINES (style=lined) --- A length of pipe, show in bold on the network diagram below, has been damaged and will be replaced with a larger pipe. --- 3 WORK AREA LINES (style=lined) ---
a. `text(Storm water from Source 2 cannot reach Outlet 1)` `:.\ text(Maximum rates are)` `text(Outlet 1: 700 kL/min)` `text(Outlet 2: 700 kL/min)` c. `text(The next smallest cut in the lower pipe system is 800.)` `:.\ text(The minimum flow through the new pipe that will achieve)` `text(this is 300 kL/min.)`Show Worked Solution
♦ Mean mark of all parts (combined) was 35%.
b.
`text(The minimum cut includes the 200 kL/min pipe from Source 1.)`
