smc-1138-50-Unknown Edge

Networks, STD2 N2 SM-Bank 30

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) ---

Show Answers Only

`BE > 500, AC > 450`

Show Worked Solution

`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)`

Networks, STD2 N2 2016 FUR1 4 MC

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

Show Answers Only

`D`

Show Worked Solution

`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`

Networks, STD2 N2 2007 FUR1 7 MC

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

A. `x = 1 and y = 7`

B. `x = 2 and y = 5`

C. `x = 3 and y = 5`

D. `x = 4 and y = 5`

Show Answers Only

`C`

Show Worked Solution

`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`

Networks, STD2 N2 2006 FUR1 4 MC

The minimal spanning tree for the network above will include the edge that has a weight of

A. `3`

B. `6`

C. `8`

D. `9`

Show Answers Only

`D`

Show Worked Solution

`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:)`

`rArr D`