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.
--- 0 WORK AREA LINES (style=lined) ---
--- 2 WORK AREA LINES (style=lined) ---
a. \(\text{MST:}\ AD,\ DB,\ DE,\ EG,\ BC\text{ and }DF.\)
b. \(\text{Find weight of the MST:}\)
\(\text{Weight}\ =1+1+2+3+3+3=13\)
The diagram shows a network with weighted edges. --- 0 WORK AREA LINES (style=lined) --- --- 3 WORK AREA LINES (style=lined) --- a. b. \(\text{Yes.}\) \(\text{The edge}\ FC\ \text{on the MST above could be replaced by the edge}\ BC\) \(\text{to create a second MST (with equivalent weight = 24)}\) a. b. \(\text{Yes.}\) \(\text{The edge}\ FC\ \text{on the MST above could be replaced by the edge}\ BC\) \(\text{to create a second MST (with equivalent weight = 24)}\)
Show Answers Only
Show Worked Solution
♦ Mean mark 53%.
♦♦♦ Mean mark 16%.
A weighted network diagram is shown below.
What is the weight of the minimum spanning tree?
`text(One Strategy – Using Kruskal’s Algorithm:)`
`text(There are 5 vertices, so we need 4 edges.)`
`:.\ text(Weight)= 4 + 4 + 5 + 6= 19`
`=>B`
In a separate diagram or on the diagram above, show the minimum spanning tree. (2 marks)
--- 0 WORK AREA LINES (style=lined) ---
`text(One strategy – Using Kruskal’s algorithm:)`
`text(Edges 1 – 5: AB, BC, DG, DH and EI)`
`text(Edges 6 – 8: CD, EF and HI)`
`(text(note AC cannot be chosen → creates a cycle))`
`text(NB: There is more than one minimal spanning tree in this)`
`text{circuit (having a weight of 19).}`
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) ---
`text(One Strategy – Using Prim’s algorithm:)`
`text(6 vertices → 5 edges on spanning tree)`
`text(Starting at vertex A)`
`text(Edge 1: AC)`
`text(Edge 2: AD)`
`text{Edge 3: DE (reject CD which creates a cycle)}`
`text(Edge 4: EF)`
`text(Edge 5: FB)`
Complete the minimal spanning tree of the network above on the diagram below. (2 marks)
--- 0 WORK AREA LINES (style=lined) ---
`text(One Strategy: Using Prim’s algorithm)`
`text(6 vertices → need 5 edges.)`
`text{Starting at vertex A (any vertex can be chosen)}`
`text(1st Edge: AB)`
`text{2nd Edge: AC (BF also possible)}`
`text(3rd Edge: CD)`
`text(4th Edge: BF)`
`text(5th Edge: AS)`
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 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) ---
a. `4`
b. `text(One of many possibilities)`
a. `text(Minimum number of edges = 4)`
b. `text(One of many possibilities,)`
For the network above, the length of the minimal spanning tree is
`text(Using Kruskal’s algorithm:)`
`text{Edge 1: 2 (least weight)}`
`text(Edge 2: 3)`
`text(Edge 3: 4)`
`text(Edges 4-5: 5)`
`text{Edges 6-7: 8 (unused edges with weights <8 create circuits and are ignored)}`
`:.\ text(Minimal spanning tree)= 2+3+4+5+5+8+8= 35`
`=> C`
