SmarterEd

Aussie Maths & Science Teachers: Save your time with SmarterEd

Networks, GEN2 2023 VCAA 13

The state has nine landmarks, and .

The edges on the graph represent the roads between the landmarks.

The numbers on each edge represent the length, in kilometres, along each road.
 

 

Three friends, Eden, Reynold and Shyla, meet at landmark .

  1. Eden would like to visit landmark .
  2. What is the minimum distance Eden could travel from to ?  (1 mark)

  3. Reynold would like to visit all the landmarks and return to .
  4. Write down a route that Reynold could follow to minimise the total distance travelled.  (1 mark)

  5. Shyla would like to travel along all the roads.
  6. To complete this journey in the minimum distance, she will travel along two roads twice.
  7. Shyla will leave from landmark but end at a different landmark.
  8. Complete the following by filling in the boxes provided.  
  9. The two roads that will be travelled along twice are the roads between:  (1 mark)

Show Answers Only

a.   


 

b.   


 

c.   

Show Worked Solution

a.   


 

b.   

♦ Mean mark (b) 44%.

c.   

♦♦♦ Mean mark (c) 12%.

NETWORKS, FUR2 2020 VCAA 3

A local fitness park has 10 exercise stations: to .

The edges on the graph below represent the tracks between the exercise stations.

The number on each edge represents the length, in kilometres, of each track.
 


 

The Sunny Coast cricket coach designs three different training programs, all starting at exercise station .

  Training program 
number		 Training details
  1 The team must run to exercise station .
  2 The team must run along all tracks just once.
  3 The team must visit each exercise station and return to  exercise station .

 

  1. What is the shortest distance, in kilometres, covered in training program 1?  (1 mark)

  2.  i. What mathematical term is used to describe training program 2?   (1 mark)

  3. ii. At which exercise station would training program 2 finish?  (1 mark)

  4. To complete training program 3 in the minimum distance, one track will need to be repeated.

     

    Complete the following sentence by filling in the boxes provided.  (1 mark)


    This track is between exercise station   
     
    		 and exercise station   
     
Show Answers Only
  2.  i.
  3. ii.
Show Worked Solution
a.  
   
   

 

b.i. 
 

b.ii. 

♦♦ Mean mark part (c) 25%.

 

c.   

NETWORKS, FUR2 2018 VCAA 4

Parcel deliveries are made between five nearby towns, to .

The roads connecting these five towns are shown on the graph below. The distances, in kilometres, are also shown.
 

A road inspector will leave from town to check all the roads and return to town when the inspection is complete. He will travel the minimum distance possible.

  1.  How many roads will the inspector have to travel on more than once?   (1 mark)

  2.  Determine the minimum distance, in kilometres, that the inspector will travel.   (1 mark)

Show Answers Only
Show Worked Solution

a.  

♦♦ Mean mark 31%.

 

b.  

♦♦♦ Mean mark 14%.


 

NETWORKS, FUR2 2018 VCAA 2

In one area of the town of Zenith, a postal worker delivers mail to 10 houses labelled as vertices to on the graph below.
 

  1. Which one of the vertices on the graph has degree 4?   (1 mark)

For this graph, an Eulerian trail does not currently exist.

  1. For an Eulerian trail to exist, what is the minimum number of extra edges that the graph would require.   (1 mark)

  2. The postal worker has delivered the mail at and will continue her deliveries by following a Hamiltonian path from .

     

    Draw in a possible Hamiltonian path for the postal worker on the diagram below.   (1 mark)

 

Show Answers Only
  3.  
Show Worked Solution

a.   
 

b.


 

c.  
 


 

NETWORKS, FUR2 2016 VCAA 2

The suburb of Alooma has a skateboard park with seven ramps.

The ramps are shown as vertices , , , , , and on the graph below.
 

 

The tracks between ramps and and between ramps and are rough, as shown on the graph above.

  1. Nathan begins skating at ramp and follows an Eulerian trail.

     

    At which ramp does Nathan finish?   (1 mark)

  2. Zoe begins skating at ramp and follows a Hamiltonian path.

     

    The path she chooses does not include the two rough tracks.

     

    Write down a path that Zoe could take from start to finish.   (1 mark)

  3. Birra can skate over any of the tracks, including the rough tracks.

     

    He begins skating at ramp and will complete a Hamiltonian cycle.

     

    In how many ways could he do this?   (1 mark) 

Show Answers Only

Show Worked Solution

a.  

“XYZWVZUYTU`


  

b.  


  

c.  

♦♦ Mean mark 31%.

NETWORKS, FUR1 2008 VCAA 5 MC

A connected planar graph has five vertices, , , , and .

The degree of each vertex is given in the following table.
 

networks-fur1-2008-vcaa-5-mc
 

Which one of the following statements regarding this planar graph is true?

A.   The sum of degrees of the vertices equals 15.

B.   It contains more than one Eulerian path.

C.   It contains an Eulerian circuit.

D.   Euler’s formula    could not be used.

E.   The addition of one further edge could create an Eulerian path.

Show Answers Only

Show Worked Solution

♦ Mean mark 41%.

NETWORKS, FUR1 2011 VCAA 9 MC

An Euler path through a network commences at vertex  and ends at vertex .

Consider the following five statements about this Euler path and network.

•  In the network, there could be three vertices with degree equal to one.

•  The path could have passed through an isolated vertex.

•  The path could have included vertex more than once.

•  The sum of the degrees of vertices and could equal seven.

•  The sum of the degrees of all vertices in the network could equal seven.

How many of these statements are true?

A.   

B.   

C.   

D.   

E.   

Show Answers Only

Show Worked Solution

♦♦ Mean mark 30%.

NETWORKS, FUR1 2011 VCAA 6 MC

A store manager is directly in charge of five department managers.

Each department manager is directly in charge of six sales people in their department.

This staffing structure could be represented graphically by

A.   a tree.

B.   a circuit.

C.   an Euler path.

D.   a Hamiltonian path.

E.   a complete graph.

Show Answers Only

Show Worked Solution

NETWORKS, FUR2 2007 VCAA 2

The estate has large open parklands that contain seven large trees.

The trees are denoted as vertices to on the network diagram below.

Walking paths link the trees as shown.

The numbers on the edges represent the lengths of the paths in metres.
 

NETWORKS, FUR2 2007 VCAA 2

  1. Determine the sum of the degrees of the vertices of this network.   (1 mark)

  2. One day Jamie decides to go for a walk that will take him along each of the paths between the trees.

    He wishes to walk the minimum possible distance.


    i.     State a vertex at which Jamie could begin his walk?   (1 mark)

  3. ii. Determine the total distance, in metres, that Jamie will walk.   (1 mark)

Michelle is currently at .

She wishes to follow a route that can be described as the shortest Hamiltonian circuit.

  1. Write down a route that Michelle can take.   (1 mark) 
Show Answers Only


Show Worked Solution

a.   

♦ Mean mark of all parts (combined) 44%.


  

b.i.   


  

b.ii.   

MARKER’S COMMENT: Many students incorrectly found the shortest Hamiltonian path.

c.    

NETWORKS, FUR1 2014 VCAA 6-7 MC

Consider the following four graphs.
 


 

Part 1

How many of these four graphs have an Eulerian circuit?

A. 

B. 

C. 

D. 

E. 

 

Part 2

How many of these four graphs are planar?

A. 

B. 

C. 

D. 

E. 

Show Answers Only

Show Worked Solution

 

♦♦♦ Mean mark part 2: 7%!
MARKER’S COMMENT: A majority of students chose option A, not understanding that a graph with intersecting edges can still be planar.

 

 

NETWORKS, FUR1 2014 VCAA 1 MC

The graph below shows the roads connecting four towns: Kelly, Lindon, Milton and Nate.


A bus starts at Kelly, travels through Nate and Lindon, then stops when it reaches Milton.

The mathematical term for this route is

A.  a loop.

B.  an Eulerian path.

C.  an Eulerian circuit.

D.  a Hamiltonian path.

E.  a Hamiltonian circuit.

Show Answers Only

Show Worked Solution

 

NETWORKS, FUR2 2008 VCAA 2

Four children, James, Dante, Tahlia and Chanel each live in a different town. 

The following is a map of the roads that link the four towns, , , and .
 

NETWORKS, FUR2 2008 VCAA 21
 

  1. How many different ways may a vehicle travel from town to town without travelling along any road more than once?   (1 mark)

James’ father has begun to draw a network diagram that represents all the routes between the four towns on the map. This is shown below.


NETWORKS, FUR2 2008 VCAA 22
 

In this network, vertices represent towns and edges represent routes between tow

  1. i. One more edge needs to be added to complete this network. Draw in this edge clearly on the diagram above.   (1 mark)

  2. ii. With reference to the network diagram, explain why a motorist at could not drive each of these routes once only and arrive back at .   (1 mark)

Show Answers Only
  2. i.  

networks-fur2-2008-vcaa-2-answer

b.ii. 

Show Worked Solution

a.  

♦♦ Exact data unavailable but “few students” answered this question correctly.

 

b.i.    networks-fur2-2008-vcaa-2-answer

 

b.ii.   

MARKER’S COMMENT: Be specific! Note that “an Eulerian circuit requires all vertices of an even degree” did not gain a mark here.

   

   

   

   

NETWORKS, FUR2 2009 VCAA 3

The city of Robville contains eight landmarks denoted as vertices to on the network diagram below. The edges on this network represent the roads that link the eight landmarks.
 


  

  1. Write down the degree of vertex .  (1 mark)

  2. Steven wants to visit each landmark, but drive along each road only once. He will begin his journey at landmark .
    1. Michael was the best player in 2014 and he considered purchasing cricket equipment that was valued at $750.
    2. At which landmark must he finish his journey?   (1 mark)
    3. Regardless of which route Steven decides to take, how many of the landmarks (including those at the start and finish) will he see on exactly two occasions?   (1 mark)
  3. Cathy decides to visit each landmark only once.
    1. Suppose she starts at , then visits and finishes at .
    2. Write down the order Cathy will visit the landmarks.   (1 mark)

    3. Suppose Cathy starts at , then visits but does not finish at .
    4. List three different ways that she can visit the landmarks.   (1 mark)

Show Answers Only






Show Worked Solution

a.  

b.i.   

b.ii.   

c.i.   

c.ii.   

NETWORKS, FUR2 2010 VCAA 3

The following network diagram shows the distances, in kilometres, along the roads that connect six intersections , , , , and .
 

  1. If a cyclist started at intersection and cycled along every road in this network once only, at which intersection would she finish?  (1 mark)

  2. The next challenge involves cycling along every road in this network at least once.

     

    Teams have to start and finish at intersection .

     

    The blue team does this and cycles the shortest possible total distance.

     

    i. Apart from intersection , through which intersections does the blue team pass more than once?   (1 mark)

  3. ii. How many kilometres does the blue team cycle?   (1 mark)

  4. The red team does not follow the rules and cycles along a bush path that connects two of the intersections.

     

    This route allows the red team to ride along every road only once.

     

    Which two intersections does the bush path connect?   (1 mark)

Show Answers Only
Show Worked Solution

a.  
  

b.i.  


  

b.ii.   


  

c.   

NETWORKS, FUR2 2011 VCAA 1

Aden, Bredon, Carrie, Dunlop, Enwin and Farnham are six towns.

The network shows the road connections and distances between these towns in kilometres.

 

  1. In kilometres, what is the shortest distance between Farnham and Carrie?   (1 mark)

  2. How many different ways are there to travel from Farnham to Carrie without passing through any town more than once?   (1 mark)

An engineer plans to inspect all of the roads in this network.

He will start at Dunlop and inspect each road only once.

  1. At which town will the inspection finish?   (1 mark)

Another engineer decides to start and finish her road inspection at Dunlop.

If an assistant inspects two of the roads, this engineer can inspect the remaining six roads and visit each of the other five towns only once.

  1. How many kilometres of road will the assistant need to inspect?   (1 mark)

Show Answers Only
Show Worked Solution

a.  


  

b.  


  

c.   


  

d.  

NETWORKS, FUR2 2013 VCAA 1

The vertices in the network diagram below show the entrance to a wildlife park and six picnic areas in the park: , , , , and .

The numbers on the edges represent the lengths, in metres, of the roads joining these locations.

 

 

  1. In this graph, what is the degree of the vertex at the entrance to the wildlife park?   (1 mark)

  2. What is the shortest distance, in metres, from the entrance to picnic area ?   (1 mark)

  3. A park ranger starts at the entrance and drives along every road in the park once.
  4. i. At which picnic area will the park ranger finish?   (1 mark)

  5. ii. What mathematical term is used to describe the route the park ranger takes?   (1 mark)

  6. A park cleaner follows a route that starts at the entrance and passes through each picnic area once, ending at picnic area .

     

    Write down the order in which the park cleaner will visit the six picnic areas.   (1 mark)

Show Answers Only
  3. i.
    ii.  
Show Worked Solution

a.  
  

b.  


  

c.i.   


  

c.ii.   
  

d.  

NETWORKS, FUR2 2014 VCAA 3

The diagram below shows a network of train lines between five towns: Attard, Bower, Clement, Derrin and Eden.

The numbers indicate the distances, in kilometres, that are travelled by train between connected towns.
 

Charlie followed an Eulerian path through this network of train lines.

  1. i. Write down the names of the towns at the start and at the end of Charlie’s path.   (1 mark)

    ii. What distance did he travel?   (1 mark)

Brianna will follow a Hamiltonian path from Bower to Attard.

  1. What is the shortest distance that she can travel?   (1 mark)

The train line between Derrin and Eden will be removed. If one other train line is removed from the network, Andrew would be able to follow an Eulerian circuit through the network of train lines.

  1. Which other train line should be removed?

     

    In the boxes below, write down the pair of towns that this train line connects.  (1 mark) 

     
    NETWORKS, FUR2 2014 VCAA 32

Show Answers Only
  1.  i. 
    ii.  
Show Worked Solution

a.i.   
  

a.ii.  


  

b.  

 

  
c.   

NETWORKS, FUR2 2012 VCAA 1

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. Determine the shortest distance between the house and the pump.   (1 mark)

    2. How many vertices on the network diagram have an odd degree?   (1 mark)
    3. The total length of all edges in the network is 1180 metres.
    4. A journey starts and finishes at the house and travels along every edge in the network.
    5. Determine the shortest distance travelled.   (1 mark)

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.

    1. On the diagram below, draw the minimum length of pipe that is needed to supply water to all locations on the farm.   (1 mark)

       

     NETWORKS, FUR2 2012 VCAA 1

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

Show Answers Only

  1. i.  
    ii. 
    iii.
  2. i.
    NETWORKS, FUR2 2012 VCAA 1 Answer
    ii.

Show Worked Solution

a.i.   

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

  

a.ii.  
 

a.iii.   

♦♦ “Very poorly answered”.
MARKER’S COMMENT: An Euler circuit is optimal but not possible here because of the two odd degree vertices.

   

   

   

   

 

 

b.i.    NETWORKS, FUR2 2012 VCAA 1 Answer

 

b.ii.