Aussie Maths & Science Teachers: Save your time with SmarterEd
The network shows the distances, in kilometres, along a series of roads that connect towns.
What is the value of the largest weighted edge included in the minimum spanning tree for this network?
\(\text{Minimum spanning tree:}\)
\(\text{Using Kruskal’s algorithm:}\)
\(\text{Edge 1 = 4, Edge 2/3 = 4, Edge 4 = 6, Edge 5 = 9}\)
\(\therefore\ \text{The largest weighted edge in the MST = 9.}\)
\(\Rightarrow C\)
Eight houses in an estate are to be connected to the internet via underground cables.
The network below shows the possible connections between the houses.
The vertices represent the houses.
The numbers on the edges represent the length of cable connecting pairs of houses, in metres.
The graph that represents the minimum length of cable needed to connect all the houses is
The table below shows the distances, in kilometres, between a number of towns.
--- 0 WORK AREA LINES (style=lined) ---
a.
b. `text{Using Prim’s algorithm (starting at}\ Y):`
`text{1st edge:}\ YC`
`text{2nd edge:}\ CB`
`text{3rd edge:}\ SB`
`text{4th edge:}\ YM`
`text{Length of minimum spanning tree}`
`=275 + 150+60+530`
`=1015\ text{km}`
A network of roads connecting towns in an alpine region is shown below.
The distances between neighbouring towns, represented by vertices, are given in kilometres.
The region receives a large snowfall, leaving all roads between the towns closed to traffic.
To ensure each town is accessible by car from every other town, some roads will be cleared.
The minimal total length of road, in kilometres, that needs to be cleared is
`text{A partial minimal spanning tree can be drawn:}`
`text{Consider each option:}`
`A:\ text{If} \ x=50 \ text{(include),} \ y = 55 \ text{(include)}`
`-> \ text{Total length} = 251 + 50 + 55 != 361 \ text{(incorrect)}`
`B:\ text{If} \ x=50 \ text{(include),} \ y = 60 \ text{(include)}`
`-> \ text{Total length} = 251 + 50 + 55 = 356 \ text{(correct)}`
`text{Similarly, options} \ C, D, E \ text{can be shown to be incorrect.}`
`=> B`
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{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`
| b. | `text{Fastest route}\ (Q\ text(to)\ U)` | `= 45 + 20` |
| `= 65 \ text{minutes}` |
The following diagram shows the distances, in metres, along a series of cables connecting a main server to seven points, `A` to `G`, in a computer network.
Calculate the minimum length of cable, in metres, required to ensure that each of the seven points is connected to the main server directly or via another point. (2 marks)
--- 4 WORK AREA LINES (style=lined) ---
`text(Using Prim’s Algorithm:)`
`text{Edge 1: main server to D (15)}`
`text{Edge 2: DE (28)}`
`text{Edge 3: EG (30)}`
`text{Edge 4: GF (32)}`
`text{Edge 5: EA (35)}`
`text{Edge 6: AB (28)}`
`text{Edge 7: GC (35)}`
`:.\ text(Minimum length)`
`= 15 + 28 + 30 + 32 + 35 + 28 + 35`
`= 203\ text(m)`
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)
--- 6 WORK AREA LINES (style=lined) ---
--- 1 WORK AREA LINES (style=lined) ---
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(Maximum length = 4 + 5 + 3 + 2 + 1 + 5 + 5 = 25 km)`
b. `text(Shortest Path is)\ CGHE`
This diagram shows the possible paths (in km) for laying gas pipes between various locations.
Gas is be supplied from one location. Any one of the locations can be the source of the supply.
What is the minimum total length of the pipes required to provide gas to all the locations?
`text(Using Kruskul’s Theorem:)`
`=>\ text(5 vertices – 4 edges needed)`
`text{Edge 1: The Hill → Carnie (9)}`
`text{Edge 2: Carnie → Bally (10)}`
`text{Edge 3: Bally → Eden (13)}`
`text{Edge 4: Carnie → Shallow End (14)}`
| `:.\ text(Maximum length)` | `= 9 + 10 + 13 + 14` |
| `= 46\ text(km)` |
`=>\ text(A)`
This diagram shows the possible paths (in km) for laying gas pipes between various locations.
Gas is to be supplied from one location. Any one of the locations can be the source of the supply.
What is the minimum total length of the pipes required to provide gas to all the locations?
| A. | 32 km |
| B. | 34 km |
| C. | 36 km |
| D. | 38 km |
`text(Using Kruskal’s Algorithm:)`
`text(1st edge: Parkview – Summerville)\ (5)`
`text(2nd edge: Summerville – Newville)\ (8)`
`text(3rd edge: Beachview – Summerville)\ (10)`
`text(4th edge: Old Town – Newville)\ (11)`
`:.\ text(Minimum length of pipes.)`
`= 5 + 8 + 10 + 11`
`= 34`
`=> B`
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) ---
i. `2\ text{(the house and the top right vertex)}`
ii. `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…)`
iii. `text(Minimum spanning tree)`
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. `text{Minimum spanning tree}`
b.
a. `text{Minimum spanning tree.}`
b. `text(Using Kruskal’s Algorithm)`
`text(Edge 1: 50)`
`text(Edges 2–3: 100)`
`text{Edge 4: 150 (ignore the 150 edge that creates a circuit)}`
`text{Edges 5–6: 200 (ignore the 200 edge that creates a circuit)} `
`text(Edge 7: 300)`
`text(Edge 8: 400)`
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) ---
a. `text(Using Prim’s Algorithm)`
`text(Starting at bottom right vertex)`
`text{1st Edge: 50}`
`text{2nd Edge: 40`
`text(3rd Edge: 50)`
`text(4th Edge: 40 etc…)`
b. `text(Total length of water pipe)`
`= 50+40+50+40+50+60+40+60+60+60`
`= 510\ text(metres)`
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`
The vertices of the graph above represent nine computers in a building. The computers are to be connected with optical fibre cables, which are represented by edges. The numbers on the edges show the costs, in hundreds of dollars, of linking these computers with optical fibre cables.
Based on the same set of vertices and edges, which one of the following graphs shows the cable layout (in bold) that would link all the computers with optical fibre cables for the minimum cost?
