Aussie Maths & Science Teachers: Save your time with SmarterEd
Consider the following weighted graph.
The minimum spanning tree for this graph contains the edge with weight \(w\).
The length of this minimum spanning tree is
\(\text{Minimum spanning tree:}\)
\(5+6+4+w+2+4+5+3+6+5+4=44+w\)
\(\Rightarrow B\)
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 + 60 = 361 \ text{(correct)}`
`text{Similarly, options} \ C, D \ text{can be shown to be incorrect.}`
`=> B`
The network below shows the distances, in metres, between camp sites at a camping ground that has electricity.
The vertices `A` to `I` represent the camp sites.
The minimum length of cable required to connect all the camp sites is 53 m.
The value of `x`, in metres, is at least
An amusement park has five toilet areas, `A`, `B`, `C`, `D` and `E`, which are connected by pathways.
The table shows the length of some of the pathways, in metres.
The following network diagram is drawn to represent this information and a correct minimum spanning tree is shown by the solid lines.
Complete the network diagram including a possible value for each of the two edges `AC` and `BE`, and justify why `AC` and `BE` were not included as part of the minimum spanning tree. (3 marks)
--- 4 WORK AREA LINES (style=lined) ---
`BE > 500, AC > 450`
`text(Consider Kruskal’s algorithm for the given minimum spanning tree:)`
`CB ->\ text{1st edge (200 – minimum weight)}`
`BD ->\ text{2nd edge (300)}`
`AD ->\ text{3rd edge (450)}`
`=> AC=460\ \ text{(choose any value such that}\ \ AC>450)`
`DE ->\ text{4th edge (500)}`
`=> BE=510\ \ text{(choose any value such that}\ \ BE>500)`
`:. BE > 500\ (BE\ text(must be greater than)\ DE)`
`:. AC > 450\ (AC\ text(must be greater than)\ AD)`
The minimum spanning tree for the network below includes the edge with weight labelled `k`.
The total weight of all edges for the minimum spanning tree is 33.
The value of `k` is
`text(Include)\ k\ text(as a given edge before using Kruskal’s Algorithm,)`
`text(Edge 1:)\ k`
`text(Edge 2: 1)`
`text(Edges 3−4: 2)`
`text(Edge 4: 3 etc…)`
`:.\ text(Minimum spanning tree)`
| `text(Total weight)` | `= k + 1+2+2+3+4+5+5+6` |
| `33` | `= k + 28` |
| `:. k` | `= 5` |
`=> D`
The minimal spanning tree for the network below includes two edges with weightings `x` and `y.`
The length of the minimal spanning tree is 19.
The values of `x` and `y` could be
`text{Using Kruskal’s Algorithm (as a guide),}`
`text(Minimum spanning tree must be:)`
| `:. 19` | `= y + 3 + x + 2 + 1 + 5` |
| `8` | `= x + y` |
`=> C`
The minimal spanning tree for the network above will include the edge that has a weight of
`text(Using Kruskal’s Algorithm:)`
`text{Edge 1: 1 (minimum weight)}`
`text(Edge 2: 2)`
`text{Edge 3: 4 (edge weight 3 creates a circuit and is ignored)}`
`text(Edge 4: 5 etc…)`
`:.\ text(Minimum spanning tree is:)`
`=>D`