The diagram shows a network with weighted edges. --- 0 WORK AREA LINES (style=lined) --- --- 3 WORK AREA LINES (style=lined) --- a. \(\text{→ The edge}\ FC\ \text{on the MST above could be replaced by the edge}\ BC\ \text{to create}\) \(\text{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}\) \(\text{a second MST (with equivalent weight = 24)}\)
b. \(\text{Yes.}\)
Networks, STD2 N2 2023 HSC 19
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. `text{Using Djikstra’s Algorithm:}` `=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` `:.\ text{Given tree is NOT a MST.}`
Show Worked Solution
`text{Shortest route}`
`=ABFGD`
`=3+1+5+5`
`=14`
b. `text{Total time of given spanning tree}`
♦ Mean mark (b) 47%.
Networks, STD2 N2 2020 HSC 18
The diagram represents a network with weighted edges.
- Draw a minimum spanning tree for this network and determine its length. (3 marks)
--- 7 WORK AREA LINES (style=lined) ---
- The network is revised by adding another vertex, `K`. Edges `AK` and `CK` have weights of 12 and 10 respectively, as shown.
What is the length of the minimum spanning tree for this revised network? (1 mark)
--- 1 WORK AREA LINES (style=lined) ---
Show Answers Only
- `text(Length = 14)`
`text(One of many possibilities:)`
- `24`
Show Worked Solution
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` |
Networks, STD2 N2 SM-Bank 26 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 SM-Bank 9
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 SM-Bank 8
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 SM-Bank 7 MC
How many spanning trees are possible for this network?
| A. | `3` |
| B. | `8` |
| C. | `14` |
| D. | `30` |
Show Worked Solution
`text(S)text(ince there are 6 vertices, each spanning tree will have)`
`text{5 edges (with no cycles).}`
`text(Consider if A and B are not connected, possible spanning)`
`text(trees are:)`
`text(3 other spanning trees exist when BF is not connected, and likewise)`
`text(when EF and ED are not connected.)`
`text(Finally, 2 other spanning trees exist when AD and AC are removed, and)`
`text(when AD and CD are removed.)`
| `:.\ text(Total spanning trees)` | `= 4 xx 3 + 2` |
| `= 14` |
Networks, STD2 N2 SM-Bank 4
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 SM-Bank 3
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`