SmarterEd

Aussie Maths & Science Teachers: Save your time with SmarterEd

Networks, STD1 N1 2022 HSC 20

The table below shows the distances, in kilometres, between a number of towns.
 

  1. Using the vertices given, draw a weighted network diagram to represent the information shown in the table.  (2 marks)
     

     
  2. A tourist wishes to visit each town.
  3. Draw the minimum spanning tree which will allow for this AND determine its length.  (3 marks)
     

Show Answers Only
  1.  
     
     
  2.   
     
  3. `1015\ text{km}`
Show Worked Solution

a. 

b.   `text{Using Prim’s algorithm (starting at}\ Y):`

`text{1st edge:}\ YC`

`text{2nd edge:}\ CB`

`text{3rd edge:}\ SB`

`text{4th edge:}\ YM`

`text{Length of minimum spanning tree}`

`=275 + 150+60+530`

`=1015\ text{km}`

Networks, STD1 N1 2021 HSC 17

The network diagram shows the travel times in minutes along roads connecting a number of different towns.
 


 

  1. Draw a minimum spanning tree for this network and determine its length.  (3 marks)

  2. How long does it take to travel from Queentown to Underwood using the fastest route?  (1 mark)

Show Answers Only
  1. `\text{See Worked Solutions}`
  2. `65 \ \text{minutes}`
Show Worked Solution

a.   `text{Using Prim’s algorithm (starting at}\ W):`

♦ Mean mark part (a) 40%.

`text(1st edge:)\ \ WM`

`text(2nd edge:)\ \ WP`

`text(3rd/4th edges:)\ \ MU\ text(and)\ \ WF`

`text(5th edge:)\ \ MK`

`text(6th edge:)\ \ KQ`

`text(7th edge:)\ \ PC`

 

`text{Length of minimum spanning tree} \ = 160` 
 
b.   `text{Fastest route}\ (Q\ text(to)\ U)` `= 45 + 20`
    `= 65 \ text{minutes}`

Networks, STD2 N2 2020 HSC 18

The diagram represents a network with weighted edges.
 


 

  1. Draw a minimum spanning tree for this network and determine its length.   (3 marks)

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

Show Answers Only
  1. `text(Length = 14)`

     

    `text(One of many possibilities:)`
     

  2. `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 34

The following diagram shows the distances, in metres, along a series of cables connecting a main server to seven points, `A` to `G`, in a computer network.
 


 

Calculate the minimum length of cable, in metres, required to ensure that each of the seven points is connected to the main server directly or via another point.   (2 marks)

Show Answers Only

`203\ text(m)`

Show Worked Solution

`text(Using Prim’s Algorithm:)`

`text{Edge 1: main server to D (15)}`

`text{Edge 2: DE (28)}`

`text{Edge 3: EG (30)}`

`text{Edge 4: GF (32)}`

`text{Edge 5: EA (35)}`

`text{Edge 6: AB (28)}`

`text{Edge 7: GC (35)}`
 

`:.\ text(Minimum length)`

`= 15 + 28 + 30 + 32 + 35 + 28 + 35`

`= 203\ text(m)`

Networks, STD2 N2 2019 HSC 30

The network diagram shows the tracks connecting 8 picnic sites in a nature park. The vertices `A` to `H` represents the picnic sites. The weights on the edges represent the distance along the tracks between the picnic sites, in kilometres.
 


 

  1. Each picnic site needs to provide drinking water. The main water source is at site `A`.

     

    Draw a minimum spanning tree and calculate the minimum length of water pipes required to supply water to all the sites if the water pipes can only be laid along the tracks.  (2 marks)

  2. One day, the track between `C` and `H` is closed. State the vertices that identify the shortest path from `C` to `E` that avoids the closed track.  (1 mark)

Show Answers Only
  1. `text(25 km)`
  2. `CGHE`
Show Worked Solution

a.   `text(One strategy – using Prim’s algorithm:)`

`text(Starting at)\ A`

`text(1st edge -)\ AB,\ \ text(2nd edge -)\ BC`

`text(3rd edge -)\ CH,\ \ text(4th edge -)\ HG`

`text(5th edge -)\ GF,\ \ text(6th edge -)\ HD`

`text(7th edge -)\ DE\ text(or)\ HE`
 

`text(Maximum length = 4 + 5 + 3 + 2 + 1 + 5 + 5 = 25 km)`

 

b.   `text(Shortest Path is)\ CGHE`

Networks, STD2 N2 SM-Bank 27 MC

This diagram shows the possible paths (in km) for laying gas pipes between various locations.
 

 
Gas is be supplied from one location. Any one of the locations can be the source of the supply.

What is the minimum total length of length of the pipes required to provide gas to all the locations?

  1.  46 km
  2.  48 km
  3.  50 km
  4.  52 km
Show Answers Only

`text(A)`

Show Worked Solution

`text(Using Kruskul’s Theorem:)`

`=>\ text(5 vertices – 4 edges needed)`

`text{Edge 1: The Hill → Carnie (9)}`

`text{Edge 2: Carnie → Bally (10)}`

`text{Edge 3: Bally → Eden (13)}`

`text{Edge 4: Carnie → Shallow End (14)}`
  


  

`:.\ text(Maximum length)` `= 9 + 10 + 13 + 14`
  `= 46\ text(km)`

 
`=>\ text(A)`

Networks, STD2 N2 SM-Bank 1 MC

This diagram shows the possible paths (in km) for laying gas pipes between various locations.
 

 
Gas is to be supplied from one location. Any one of the locations can be the source of the supply.

What is the minimum total length of the pipes required to provide gas to all the locations?

A. 32 km
B. 34 km
C. 36 km
D. 38 km
Show Answers Only

`B`

Show Worked Solution

`text(Using Kruskal’s Algorithm:)`
 

 
`text(1st edge: Parkview – Summerville)\ (5)`

`text(2nd edge: Summerville – Newville)\ (8)`

`text(3rd edge: Beachview – Summerville)\ (10)`

`text(4th edge: Old Town – Newville)\ (11)`

 
`:.\ text(Minimum length of pipes.)`

`= 5 + 8 + 10 + 11`

`= 34`
 

`=> B`

Networks, STD2 N2 SM-Bank 14

Water will be pumped from a dam to eight locations on a farm.

The pump and the eight locations (including the house) are shown as vertices in the network diagram below.

The numbers on the edges joining the vertices give the shortest distances, in metres, between locations.
 

NETWORKS, FUR2 2012 VCAA 1

 

  1. How many vertices on the network diagram have an odd degree?  (1 mark)

     

    The total length of all edges in the network is 1180 metres.

     

    The total length of pipe that supplies water from the pump to the eight locations on the farm is a minimum.

     

    This minimum length of pipe is laid along some of the edges in the network.

  2. On the diagram below, draw the minimum length of pipe that is needed to supply water to all locations on the farm.  (2 marks)
     
     
    NETWORKS, FUR2 2012 VCAA 1

  3. What is the mathematical term that is used to describe this minimum length of pipe?  (1 mark)

Show Answers Only
  1. `2`
  2. `1250\ text(m)`
     
    NETWORKS, FUR2 2012 VCAA 1 Answer

  3. `text(Minimum spanning tree)`
Show Worked Solution

i.   `2\ text{(the house and the top right vertex)}`

MARKER’S COMMENT: Many students, surprisingly, had problems with part (i).
 

ii.  `text(One Strategy – Using Prim’s algorithm:)`

`text(Starting at the house)`

`text(1st edge: 50)`

`text{2nd edge: 40 (either)}`

`text(3rd edge: 40)`

`text(4th edge: 60  etc…)`
 

NETWORKS, FUR2 2012 VCAA 1 Answer


iii.   `text(Minimum spanning tree)`

Networks, STD2 N2 2017 FUR2 3a

While on holiday, four friends visit a theme park where there are nine rides.

On the graph below, the positions of the rides are indicated by the vertices.

The numbers on the edges represent the distances, in metres, between rides.
 

Electrical cables are required to power the rides.

These cables will form a connected graph.

The shortest total length of cable will be used.

 

  1. Give a mathematical term to describe a graph that represents these cables.   (1 mark)

  2. Draw in the graph that represents these cables on the diagram below.   (1 mark)


 

Show Answers Only

a.   `text{Minimum spanning tree}`

b.    
       

Show Worked Solution

a.   `text{Minimum spanning tree.}`

 

b.   `text(Using Kruskal’s Algorithm)`

`text(Edge 1: 50)`

`text(Edges 2–3: 100)`

`text{Edge 4: 150 (ignore the 150 edge that creates a circuit)}`

`text{Edges 5–6: 200  (ignore the 200 edge that creates a circuit)} `

`text(Edge 7: 300)`

`text(Edge 8: 400)`
 
        

Networks, STD2 N2 2011 FUR2 2

At the Farnham showgrounds, eleven locations require access to water. These locations are represented by vertices on the network diagram shown below. The dashed lines on the network diagram represent possible water pipe connections between adjacent locations. The numbers on the dashed lines show the minimum length of pipe required to connect these locations in metres.
 

NETWORKS, FUR2 2011 VCAA 2 

 
All locations are to be connected using the smallest total length of water pipe possible.

  1. On the diagram, show where these water pipes will be placed.  (1 mark)
  2. Calculate the total length, in metres, of water pipe that is required.  ( 1 mark) 
Show Answers Only
  1.  
    NETWORKS, FUR2 2011 VCAA 2 Answer
  2. `510\ text(metres)`
Show Worked Solution

a. `text(Using Prim’s Algorithm)`

`text(Starting at bottom right vertex)`

`text{1st Edge: 50}`

`text{2nd Edge: 40`

`text(3rd Edge: 50)`

`text(4th Edge: 40   etc…)`
 

NETWORKS, FUR2 2011 VCAA 2 Answer


b.   `text(Total length of water pipe)`

`= 50+40+50+40+50+60+40+60+60+60`

`= 510\ text(metres)`

Networks, STD2 N2 2008 FUR2 1

James, Dante, Tahlia and Chanel are four children playing a game.

In this children’s game, seven posts are placed in the ground.

The network below shows distances, in metres, between the seven posts.

The aim of the game is to connect the posts with ribbon using the shortest length of ribbon.

This will be a minimal spanning tree.

 

NETWORKS, FUR2 2008 VCAA 11

  1. Draw in a minimal spanning tree for this network on the diagram below.  (1 mark)


NETWORKS, FUR2 2008 VCAA 12

  1. Determine the length, in metres, of this minimal spanning tree.  (1 mark)

  2. How many different minimal spanning trees can be drawn for this network?  (1 mark)

Show Answers Only
  1.  

    `text(or)`
  2. `16\ text(metres)`
  3. `2`
Show Worked Solution

a.  `text(Using Kruskal’s Algorithm)`

`text{Edges 1-3: 2}`

`text{Edges 4-5: 3  (2 edges with weight 3 create a circuit and are ignored)`

`text(Edge 6: 4)` 
 

`text(or)`

 

b.   `text(Length of minimal spanning tree)`

`= 2+2+2+3+3+4`

`= 16\ text(metres)`
 

c.   `2`

Networks, STD2 N2 2013 FUR1 3 MC

 
The vertices of the graph above represent nine computers in a building. The computers are to be connected with optical fibre cables, which are represented by edges. The numbers on the edges show the costs, in hundreds of dollars, of linking these computers with optical fibre cables.

Based on the same set of vertices and edges, which one of the following graphs shows the cable layout (in bold) that would link all the computers with optical fibre cables for the minimum cost?
 

 

vcaa-networks-fur1-2013-3ii

Show Answers Only

`A`

Show Worked Solution

`text(Using Prim’s algorithm)`

`text(Starting at far left vertex,)`

`text{1st edge: 2}`

`text(2nd edge: 3)`

`text{3rd edge: 4}`

`text(4th edge: 3   etc…)`

`=>  A`