SmarterEd

Aussie Maths & Science Teachers: Save your time with SmarterEd

Networks, GEN2 2024 VCAA 13

A supermarket has five departments, with areas allocated as shown on the floorplan below.
 

The floorplan is represented by the graph below.

On this graph, vertices represent departments and edges represent boundaries between two departments.

This graph is incomplete.
 

  1. Draw the missing vertex and missing edges on the graph above. Include a label.   (1 mark)

Karla is standing in the Promotional department.

She wants to visit each department in the supermarket once only.

  1.  i.  In which department will she finish?  (1 mark)
  2. ii.  What is the mathematical name for this type of journey?  (1 mark)
  3. The supermarket adds a new Entertainment department \((E)\), and the floorplan is rearranged.
  4. The boundaries between the departments are represented in the adjacency matrix below, where a ' 1 ' indicates a boundary between the departments.

\begin{aligned}
& \ \ B \ \ \ D \ \ \  E \ \ \  F \ \ \ G \ \ \ P \\
\begin{array}{c}
B\\
D \\
E \\
F \\
G \\
P
\end{array}& \begin{bmatrix}
0 & 1 & 1 & 1 & 0 & 1 \\
1 & 0 & 0 & 1 & 1 & 0 \\
1 & 0 & 0 & 0 & 0 & 1 \\
1 & 1 & 0 & 0 & 1 & 1 \\
0 & 1 & 0 & 1 & 0 & 1 \\
1 & 0 & 1 & 1 & 1 & 0
\end{bmatrix}
\end{aligned}

  1. Use the adjacency matrix to complete the floorplan below by labelling each department. The Bakery \((B)\) is already labelled.  (1 mark)

Show Answers Only

a. 

 
b.i.   \(\text{The bakery}\)

b.ii.  \(\text{Hamiltonian Path}\)
 

c.

Show Worked Solution

a. 

b.i.  \(\text{Bakery}\)

b.ii. \(\text{The path has no repeated edges or vertices, and }\)

\(\text{incudes all the edges of the graph.}\)

\(\therefore\ \text{It is a Hamiltonian Path.}\)

c.

Networks, GEN2 2023 VCAA 13

The state \(A\) has nine landmarks, \(G, H, I, J, K, L, M, N\) and \(O\).

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 \(G\).

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

  3. Reynold would like to visit all the landmarks and return to \(G\).
  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 \(G\) 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.    \(\text{Shortest path:}\ G\ K\ I\ M\)

\(\text{Minimum distance}\ = 1.5+1.2+3.2 = 5.9\ \text{km}\)
 

b.   \(\text{Find the shortest Hamiltonian cycle starting at vertex}\ G:\)

\(G\ H\ K\ I\ J\ M\ O\ L\ N\ G\)

\(G\ N\ L\ O\ M\ J\ I\ K\ H\ G\ \text{(reverse of other path)}\)
 

c.   \(\text{vertex}\ L\ \text{and vertex}\ N\)

\(\text{vertex}\ J\ \text{and vertex}\ M\)

Show Worked Solution

a.    \(\text{Shortest path:}\ G\ K\ I\ M\)

\(\text{Minimum distance}\ = 1.5+1.2+3.2 = 5.9\ \text{km}\)
 

b.   \(\text{Find the shortest Hamiltonian cycle starting at vertex}\ G:\)

\(G\ H\ K\ I\ J\ M\ O\ L\ N\ G\)

\(G\ N\ L\ O\ M\ J\ I\ K\ H\ G\ \text{(reverse of other path)}\)

♦ Mean mark (b) 44%.

c.   \(\text{Using an educated guess and check methodology:}\)

\(\text{vertex}\ L\ \text{and vertex}\ N\)

\(\text{vertex}\ J\ \text{and vertex}\ M\)

♦♦♦ Mean mark (c) 12%.

NETWORKS, FUR2 2021 VCAA 1

Maggie's house has five rooms, `A, B, C, D` and `E`, and eight doors.

The floor plan of these rooms and doors is shown below. The outside area, `F`, is shown shaded on the floor plan.
 

The floor plan is represented by the graph below.

On this graph, vertices represent the rooms and the outside area. Edges represent direct access to the rooms through the doors.

One edge is missing from the graph.
 

  1. On the graph above, draw the missing edge.   (1 mark)

  2. What is the degree of vertex `E`?   (1 mark)

  3. Maggie hires a cleaner to clean the house.
  4. It is possible for the cleaner to enter the house from the outside area, `F`, and walk through each room only once, cleaning each room as he goes and finishing in the outside area, `F`.
  5.  i. Complete the following to show one possible route that the cleaner could take.   (1 mark)

        
         
    ii. What is the mathematical term for such a journey?   (1 mark)

Show Answers Only
  1.  
  2. `2`
  3.  i. `FABEDCF\ text(or)\ FCDEBAF`
  4. ii. `text{Hamiltonian cycle}`
Show Worked Solution

a.

b.  `text{Degree} = 2`
 

c.i.  `FABEDCF\ text(or)\ FCDEBAF`

c.ii.  `text{Hamiltonian cycle}`

NETWORKS, FUR1 2021 VCAA 5 MC

Consider the following five statements about the graph above:

    • The graph is planar.
    • The graph contains a cycle.
    • The graph contains a bridge.
    • The graph contains an Eulerian trail.
    • The graph contains a Hamiltonian path.

How many of these statements are true?

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
Show Answers Only

`D`

Show Worked Solution

`text{Consider each statement}`

♦♦♦ Mean mark 17%.

`text{Graph is planar} \ -> \ text{edges only meet at vertices (TRUE)}` 

`text{Graph contains a cycle} \ -> \ text{multiple cycles exist (TRUE)}`

`text{Graph contains a bridge} \ -> \ text{the far right edge, if removed,}`

`text{would disconnect the graph (TRUE)}`

`text{Graph contains an Eulerian trail} \ -> \ text{requires two (only)}`

`text{vertices of an odd degree (FALSE)}`

`text{Graph contains a Hamiltonian path} \ -> \ text{a path that touches}`

`text{each vertex once only (TRUE)}`
  

`=> D`

NETWORKS, FUR2 2020 VCAA 3

A local fitness park has 10 exercise stations: `M` to `V`.

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

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

 

  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
  1. `3.2\ text(km)`
  2.  i. `text(Eulerian trail)`
  3. ii. `text(Station)\ P`
  4. `S and T`
Show Worked Solution
a.   `text(Shortest distance)` `= STUVO`
    `= 0.6 + 1.2 + 0.6 + 0.8`
    `= 3.2\ text(km)`

 

b.i.  `text(Eulerian trail)`
 

b.ii.  `text(Station)\ P\ text{(only other vertex with}\ S\ text{to have odd degree)} `

♦♦ Mean mark part (c) 25%.

 

c.   `S and T`

NETWORKS, FUR1 2020 VCAA 2 MC

Consider the graph below.
 


 

Which one of the following is not a Hamiltonian cycle for this graph?

  1. `ABCDFEGA`
  2. `BAGEFDCB`
  3. `CDFEGABC`
  4. `DCBAGFED`
  5. `EGABCDFE`
Show Answers Only

`D`

Show Worked Solution

`text(Hamiltonian cycle – start and finish at the same)`

`text(vertex and touch all other vertices once.)`

`text(Option)\ D\ text(is not a valid path as it needs an edge)\ E\ text(to)\ D.`

`=>  D`

NETWORKS, FUR2 2019 VCAA 1

Fencedale High School has six buildings. The network below shows these buildings represented by vertices. The edges of the network represent the paths between the buildings.
 


 

  1. Which building in the school can be reached directly from all other buildings?   (1 mark)

  2. A school tour is to start and finish at the office, visiting each building only once.
     i.     What is the mathematical term for this route?   (1 mark)

  3. ii. Draw in a possible route for this school tour on the diagram below.   (1 mark)

 

Show Answers Only
  1. `text(Office)`
  2.  i.  `text(Hamiltonian cycle)`
    ii. `text(See Worked Solutions)` 
Show Worked Solution

a.  `text(Office)`
 

b.i.   `text(Hamiltonian cycle)`

`text{(note a Hamiltonian path does not start and finish}`

  `text{at the same vertex.)}`
 

b.ii.   `text(One of many solutions:)`
 

NETWORKS, FUR2 2016 VCAA 2

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

The ramps are shown as vertices `T`, `U`, `V`, `W`, `X`, `Y` and `Z` on the graph below.
 

 

The tracks between ramps `U` and `V` and between ramps `W` and `X` are rough, as shown on the graph above.

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

     

    At which ramp does Nathan finish?   (1 mark)

  2. Zoe begins skating at ramp `X` 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 `X` and will complete a Hamiltonian cycle.

     

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

Show Answers Only
  1. `U`
  2. `XYTUZVW`
    `XYTUZWV`
  3. `4\ text(ways)`
Show Worked Solution

a.   `text{The Eulerian trail (visits each edge exactly once):}`

“XYZWVZUYTU`

`:. text(Finishes at ramp)\ U.`
  

b.   `text{Hamiltonian Paths (touch each vertex exactly once):}`

`XYTUZVW`

`XYTUZWV`
  

c.   `text(Hamiltonian cycles:)`

♦♦ Mean mark 31%.

`XYTUZVWX`

`XYTUVZWX`

`text(These two cycles can be reversed)`

`text(to add two more possibilities.)`

`XWVZUTYX`

`XWZVUTYX`

`:. 4\ text(ways.)`

NETWORKS, FUR1 2006 VCAA 3 MC

networks-fur1-2006-vcaa-3-mc
 

Which one of the following statements is true regarding the network above?

A.   `ABCDEFG` is a Hamiltonian circuit.

B.   Only one Hamiltonian path exists.

C.   `CBAGFEDC` is an Eulerian circuit.

D.   At least two Eulerian paths exist.

E.   There are no circuits.

Show Answers Only

`D`

Show Worked Solution

`text(The network has exactly 2 vertices with)`

♦ Mean mark 43%.

`text(odd-degrees.)`

`:.\ text(At least two Eulerian paths exist.)`

`rArr D`

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

`A`

Show Worked Solution

`=>  A`

NETWORKS, FUR2 2007 VCAA 2

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

The trees are denoted as vertices `A` to `G` 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 `F`.

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
  1. `24`
    1. `C\ text(or)\ G`
    2. `2800\ text(m)`

  3. `F-G-A-B-C-D-E-F,\ text(or)`
    `F-E-D-C-B-A-G-F`

Show Worked Solution

a.   `text(Sum of degrees of vertices)`

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

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

`= 24`
  

b.i.   `C\ text(or)\ G`

`text(An Euler path is required and)`

`text(therefore the starting point is at)`

`text(a vertex with an odd degree.)`
  

b.ii.   `2800\ text(m)`

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

c.    `F-G-A-B-C-D-E-F,\ text(or)`

`F-E-D-C-B-A-G-F`

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

`D`

Show Worked Solution

`text(A Hamiltonian path touches every vertex)`

`text(exactly once.)`

`=>D` 

NETWORKS, FUR2 2009 VCAA 3

The city of Robville contains eight landmarks denoted as vertices `N` to `U` 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 `U`.  (1 mark)

  2. Steven wants to visit each landmark, but drive along each road only once. He will begin his journey at landmark `N`.
    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 `S`, then visits `R` and finishes at `T`.
    2. Write down the order Cathy will visit the landmarks.   (1 mark)

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

Show Answers Only

  1. `4`
    1. `P\ text{(the other odd degree vertex)}`
    2. `5`
    1. `(SR)QPONU(T)`
    2. `text(Other paths are)`
      `(SR)QPUTNO`
      `(SR)QPONTU`
      `(SR)TUNOPQ`
      `(SR)UTNOPQ`
      `text{(only 3 paths required)}`

Show Worked Solution

a.   `4`

b.i.   `P\ text{(the other odd degree vertex)}`

b.ii.   `5 (N, T, R, P, U)`

c.i.   `(SR)QPONU(T)`

c.ii.   `text(Other paths are)`

`(SR)QPUTNO`

`(SR)QPONTU`

`(SR)TUNOPQ`

`(SR)UTNOPQ`

`text{(only 3 paths required)}`

NETWORKS, FUR2 2010 VCAA 2

The diagram below shows a network of tracks (represented by edges) between checkpoints (represented by vertices) in a short-distance running course. The numbers on the edges indicate the time, in minutes, a team would take to run along each track.

 

Network, FUR2 2011 VCAA 2_1
 

Another challenge requires teams to run from checkpoint `X` to checkpoint `Y` using these tracks.

  1. What would be the shortest possible time for a team to run from checkpoint `X` to checkpoint `Y`?  (1 mark)

  2. Teams are required to follow a route from checkpoint `X` to checkpoint `Y` that passes through every checkpoint once only.

  3.  i. What mathematical term is used to describe such a route?   (1 mark)

  4. ii. On the network diagram below, draw in the route from checkpoint `X` to checkpoint `Y` that passes through every checkpoint once only.   (1 mark)

   
  Network, FUR2 2011 VCAA 2_2

Show Answers Only
  1. `11\ text(minutes)`
  2. i. `text(Hamiltonian path)`
    ii. 
    Network, FUR2 2011 VCAA 2 Answer
Show Worked Solution

a.   `4 + 3 + 4 = 11\ text(minutes)`
  

b.i.   `text(Hamiltonian path)`

 

b.ii.    Network, FUR2 2011 VCAA 2 Answer

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
  1. `200\ text(km)`
  2. `6`
  3. `text(Bredon)`
  4. `240\ text(km)`
Show Worked Solution

a.   `text{Farnham to Carrie (shortest)}`

`= 60 + 140`

`= 200\ text(km)`
  

b.   `text(Different paths are)`

`FDC, FEDC, FEBC,`

`FEABC, FDEBC,`

`FDEABC`

`:. 6\ text(different ways)`
  

c.   `text(A possible path is)\ DFEABCDEB\ text(and will finish)`

`text{at Bredon (the other odd-degree vertex).}`
  

d.   `text(If the engineer’s path is)`

`DFEABCD,`

`text(Distance assistant inspects)`

`= 110 + 130`

`= 240\ text(km)`

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: `P1`, `P2`, `P3`, `P4`, `P5` and `P6`.

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 `P3`?   (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 `P1`.

     

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

Show Answers Only
  1. `3`
  2. `1000\ text(m)`
  3. i. `P4`
    ii. `text(Euler path)` 
  4. `E-P5-P4-P6-P3-P2-P1`
Show Worked Solution

a.   `3`
  

b.   `text( Shortest distance)`

`= E-P1-P3`

`= 600 + 400`

`= 1000\ text(m)`
  

c.i.   `text(A route could be)`

`E-P1-P2-P3-P4-P5`

`-E-P6-P1-P3-P6-P4`

`:.\ text(Finish at)\ P4\ \ text{(the other odd degree vertex)}`
  

c.ii.   `text(Euler path)`
  

d.   `E-P5-P4-P6-P3-P2-P1`

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.  `text(Bower, Eden)`
    ii.  `910\ text(km)`
  2. `270\ text(km)`
  3. `text(Bower and Derrin)`
Show Worked Solution

a.i.   `text(Bower, Eden or Eden, Bower)`
  

a.ii.   `text(Distance)\ \ BDABCDEACE`

`= 160 + 130 + 80 + 70 + 60 + 40 + 100 + 150 + 120`

`= 910\ text(km)`
  

b.   `text(Shortest Hamiltonian path is)\ BCDEA`

`text(Distance)` `= 70 + 60 + 40 + 100`
  `= 270\ text(km)`

  
c.   `text(Remove the line between Bower and Derrin.)`

NETWORKS, FUR2 2015 VCAA 2

The factory supplies groceries to stores in five towns, `Q`, `R`, `S`, `T` and `U`, represented by vertices on the graph below.
 

Networks, FUR2 2015 VCAA 2
 

The edges of the graph represent roads that connect the towns and the factory.

The numbers on the edges indicate the distance, in kilometres, along the roads.

Vehicles may only travel along the road between towns `S` and `Q` in the direction of the arrow due to temporary roadworks.

Each day, a van must deliver groceries from the factory to the five towns.

The first delivery must be to town `T`, after which the van will continue on to the other four towns before returning to the factory.

  1. i. The shortest possible circuit from the factory for this delivery run, starting from town `T`, is not Hamiltonian.
     
    Complete the order in which these deliveries would follow this shortest possible circuit.   (1 mark)

     factory – `T` – ___________________________ – factory

  2. ii. With reference to the town names in your answer to part (a)(i), explain why this shortest circuit is not a Hamiltonian circuit.   (1 mark)

  3. Determine the length, in kilometres, of a delivery run that follows a Hamiltonian circuit from the factory to these stores if the first delivery is to town `T`.   (1 mark)

Show Answers Only

a.i.  `text(factory)\-T-S-Q-R-S-U-text(factory)`

aii.  `text(The van passes through town)\ S\ text(twice.)`

b.   `162\ text(km)`

Show Worked Solution

a.i.   `text(factory)\-T-S-Q-R-S-U- text(factory)`
  

a.ii.   `text(The van passes through town)\ S\ text(twice.)`
  

b.   `text(Hamiltonian circuit is)`

`text(factory)\-T-S-R-Q-U-text(factory)`

`= 44 + 38 + 12 + 8 + 38 + 22`

`= 162\ text(km)`