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. \(\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)}\)
b. \(\text{Yes.}\)
Networks, STD2 N2 EQ-Bank 4 MC
A weighted network diagram is shown below.
What is the weight of the minimum spanning tree?
- 18
- 19
- 20
- 22
Show Worked Solution
`text(One Strategy – Using Kruskal’s Algorithm:)`
`text(There are 5 vertices, so we need 4 edges.)`
| `:.\ text(Weight)` | `= 4 + 4 + 5 + 6` |
| `= 19` |
`=>\ text(B)`
Networks, STD2 N2 EQ-Bank 32
In a separate diagram or on the diagram above, show the minimum spanning tree . (2 marks)
--- 0 WORK AREA LINES (style=lined) ---
Show Answers Only
Show Worked Solution
`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).}`
Networks, STD2 N2 EQ-Bank 23
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) ---
Show Answers Only
Show Worked Solution
`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: ED (reject CD which creates a cycle)}`
`text(Edge 4: EF)`
`text(Edge 5: BF)`
Networks, STD2 N2 EQ-Bank 27
Complete the minimal spanning tree of the network above on the diagram below. (2 marks)
--- 0 WORK AREA LINES (style=lined) ---
Show Answers Only
Show Worked Solution
`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)`
Networks, STD2 N2 EQ-Bank 25
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) ---
Show Answers Only
`text(or)`
Show Worked Solution
`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)`
Networks, STD2 N2 2007 FUR2 1
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.
- What is the minimum number of edges needed to connect the five houses? (1 mark)
--- 1 WORK AREA LINES (style=lined) ---
- On the diagram above, draw a connected graph with this number of edges. (1 mark)
--- 0 WORK AREA LINES (style=lined) ---
Show Answers Only
- `4`
-
Show Worked Solution
a. `text(Minimum number of edges = 4)`
b. `text(One of many possibilities,)`
Networks, STD2 N2 2014 FUR1 5 MC
Networks, STD2 N2 2010 FUR1 5 MC
For the network above, the length of the minimal spanning tree is
A. `30`
B. `31`
C. `35`
D. `39`
Show Worked Solution
`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`