The diagram shows a network of houses and roads, and the time taken to travel along the roads in minutes.
Aussie Maths & Science Teachers: Save your time with SmarterEd
The diagram shows a network of houses and roads, and the time taken to travel along the roads in minutes.
The diagram shows a network with weighted edges. --- 0 WORK AREA LINES (style=lined) --- --- 3 WORK AREA LINES (style=lined) ---
A network of running tracks connects the points \(A, B, C, D, E, F, G, H\), as shown. The number on each edge represents the time, in minutes, that a typical runner should take to run along each track. --- 4 WORK AREA LINES (style=lined) --- --- 4 WORK AREA LINES (style=lined) --- a. \(ABFGD\) b. \(\text{See worked solutions}\) a. \(\text{Using Djikstra’s Algorithm:}\) \(\text{Shortest route}=ABFGD=3+1+5+5=14\) b. \(\text{Total time of given spanning tree}\) \(=3+11+1+2+4+5+5=31\) \(\text{Consider the MST below:}\) \(\text{Total time (MST)}= 3+1+2+4+5+5+9=29\) \(\therefore \text{ Given tree is NOT a MST.}\)
The table below shows the distances, in kilometres, between a number of towns.
The network diagram shows the travel times in minutes along roads connecting a number of different towns.
--- 8 WORK AREA LINES (style=lined) ---
--- 2 WORK AREA LINES (style=lined) ---
a. `\text{See Worked Solutions}`
b. `65 \ \text{minutes}`
a. `text{Using Prim’s algorithm (starting at}\ W):`
`text(1st edge:)\ \ WM`
`text(2nd edge:)\ \ WP`
`text(3rd/4th edges:)\ \ MU\ text(and)\ \ WF`
`text(5th edge:)\ \ MK`
`text(6th edge:)\ \ KQ`
`text(7th edge:)\ \ PC`
The diagram represents a network with weighted edges.
--- 8 WORK AREA LINES (style=lined) ---
What is the length of the minimum spanning tree for this revised network? (1 mark)
--- 1 WORK AREA LINES (style=lined) ---
a. `text(Length = 14)`
`text(One of many possibilities:)`
b. `24`
a. `text{Using Kruskal’s Algorithm (one of many possibilities):}`
`text{Edge 1 :}\ GH\ (1)`
`text{Edge 2 :}\ FH\ (2)`
`text{Edge 3 :}\ CF\ (2)`
`text{Edge 4 :}\ FD\ (2)`
`text{Edge 5 :}\ DE\ (2)`
`text{Edge 6 :}\ BC\ (3)`
`text{Edge 7 :}\ AB\ (2)`
`text{Minimum length of spanning tree}= 1 + 2 + 2 + 2 +2 + 3 +2= 14`
b. `text{Add}\ CK \ text{to the minimum spanning tree in (a).}`
`therefore \ text(Revised length)= 14 + 10= 24`
The network diagram shows the tracks connecting 8 picnic sites in a nature park. The vertices `A` to `H` represents the picnic sites. The weights on the edges represent the distance along the tracks between the picnic sites, in kilometres.
Draw a minimum spanning tree and calculate the minimum length of water pipes required to supply water to all the sites if the water pipes can only be laid along the tracks. (2 marks)
--- 5 WORK AREA LINES (style=lined) ---
--- 1 WORK AREA LINES (style=lined) ---
a. `text(25 km)`
b. `CGHE`
a. `text(One strategy – using Prim’s algorithm:)`
`text(Starting at)\ A`
`text(1st edge)-AB,\ \ text(2nd edge)-BC`
`text(3rd edge)-CH,\ \ text(4th edge)-HG`
`text(5th edge)-GF,\ \ text(6th edge)-HD`
`text(7th edge)-DE\ text(or)\ HE`
`text(Minimum length = 4 + 5 + 3 + 2 + 1 + 5 + 5 = 25 km)`
b. `text(Shortest Path is)\ CGHE`
Highlight the minimal spanning tree of this network on the diagram above, or in a separate diagram. (2 marks)
--- 0 WORK AREA LINES (style=lined) ---
Complete the minimal spanning tree of the network above on the diagram below. (2 marks)
--- 0 WORK AREA LINES (style=lined) ---
The diagram below is a connected network.
Complete the diagram below to show the minimal spanning tree of this network. (2 marks)
--- 0 WORK AREA LINES (style=lined) ---
`text(or)`
`text(One Strategy – Kruskul’s algorithm)`
`text(There are 6 vertices, so we need 5 edges.)`
`text{Edge 1: BC (least weight) – could have chosen ED}`
`text{Edge 2: DE (next least weight)}`
`text{Edge 3: AF (could have been CD)}`
`text(Edge 4: CD)`
`text{Edge 5: CF or EF (reject CE as it creates a cycle)}`
`text(or)`
A school is designing a computer network between five key areas within the school.
The cost of connecting the rooms is shown in the diagram below.
a. `text(One Strategy: Using Prim’s Algorithm)`
`text(Starting vertex – Staff Room)`
`text(1st edge: Staff Room – Library)`
`text(2nd edge: Library – School Office)`
`text(3rd edge: Staff Room – IT Staff)`
`text(4th edge: Library – Computer Room)`
b. `text(Minimum Cost)= 300 + 300 + 400 + 500= $1500`
Water will be pumped from a dam to eight locations on a farm.
The pump and the eight locations (including the house) are shown as vertices in the network diagram below.
The numbers on the edges joining the vertices give the shortest distances, in metres, between locations.
--- 1 WORK AREA LINES (style=lined) ---
The total length of all edges in the network is 1180 metres.
The total length of pipe that supplies water from the pump to the eight locations on the farm is a minimum.
This minimum length of pipe is laid along some of the edges in the network.
--- 1 WORK AREA LINES (style=lined) ---
a. `2\ text{(the house and the top right vertex)}`
b. `text(One Strategy – Using Prim’s algorithm:)`
`text(Starting at the house)`
`text(1st edge: 50)`
`text{2nd edge: 40 (either)}`
`text(3rd edge: 40)`
`text(4th edge: 60 etc…)`
c. `text(Minimum spanning tree)`
A new housing estate is being developed.
There are five houses under construction in one location.
These houses are numbered as points 1 to 5 below.
The builders require the five houses to be connected by electrical cables to enable the workers to have a supply of power on each site.
--- 1 WORK AREA LINES (style=lined) ---
--- 0 WORK AREA LINES (style=lined) ---
While on holiday, four friends visit a theme park where there are nine rides.
On the graph below, the positions of the rides are indicated by the vertices.
The numbers on the edges represent the distances, in metres, between rides.
Electrical cables are required to power the rides.
These cables will form a connected graph.
The shortest total length of cable will be used.
--- 1 WORK AREA LINES (style=lined) ---

--- 0 WORK AREA LINES (style=lined) ---
A factory requires seven computer servers to communicate with each other through a connected network of cables.
The servers, `J`, `K`, `L`, `M`, `N`, `O` and `P`, are shown as vertices on the graph below.
The edges on the graph represent the cables that could connect adjacent computer servers.
The numbers on the edges show the cost, in dollars, of installing each cable.
--- 1 WORK AREA LINES (style=lined) ---
--- 1 WORK AREA LINES (style=lined) ---
How much would be saved in installation costs if the factory removed computer server `P` from its minimum spanning tree network?
A copy of the graph above is provided below to assist with your working. (1 mark)

--- 0 WORK AREA LINES (style=lined) ---
a. `$300`
b. `text(Minimum cost of)\ K\ text(to)\ N`
`= 440 + 480= $920`
c.i. `text(Using Prim’s Algorithm:)`
`text(Starting at Vertex)\ L`
`text{1st Edge: L → M (300)}`
`text{2nd Edge: L → K (360)}`
`text{3rd Edge: K → J (250)}`
`text{4th Edge: J → P (200) etc…}`
c.ii. `text(Disconnect)\ J – P\ text(and)\ O – P`
`text(Savings) = 200 + 400 = $600`
`text(Add in)\ M – N`
`text(C)text(ost) = $480`
`:.\ text(Net savings)= 600-480= $120`
At the Farnham showgrounds, eleven locations require access to water. These locations are represented by vertices on the network diagram shown below. The dashed lines on the network diagram represent possible water pipe connections between adjacent locations. The numbers on the dashed lines show the minimum length of pipe required to connect these locations in metres.
All locations are to be connected using the smallest total length of water pipe possible.
--- 1 WORK AREA LINES (style=lined) ---
James, Dante, Tahlia and Chanel are four children playing a game.
In this children’s game, seven posts are placed in the ground.
The network below shows distances, in metres, between the seven posts.
The aim of the game is to connect the posts with ribbon using the shortest length of ribbon.
This will be a minimal spanning tree.
--- 1 WORK AREA LINES (style=lined) ---
--- 1 WORK AREA LINES (style=lined) ---
a. `text(Using Kruskal’s Algorithm)`
`text{Edges 1-3: 2}`
`text{Edges 4-5: 3 (2 edges with weight 3 create a circuit and are ignored)`
`text(Edge 6: 4)`
`text(or)`
b. `text(Length of minimal spanning tree)`
`= 2+2+2+3+3+4= 16\ text(metres)`
c. `2`