SmarterEd

Aussie Maths & Science Teachers: Save your time with SmarterEd

Networks, GEN1 2024 VCAA 34 MC

Consider the following graph.
 

A Eulerian trail through this graph could be

  1. ABCDEF
  2. ACBDCFDEF
  3. BACBDCFDEF
  4. BDCABCDFCDEF
Show Answers Only

\(C\)

Show Worked Solution

\(\text{An Eulerian trail has exactly 2 vertices of odd degree.}\)

\(\text{You must start on one and finish on the other ie B to F.}\)

\(\rightarrow\ \text{Eliminate A and B}\)

\(\text{A path cannot be repeated}\ \rightarrow\ \text{Eliminate D}\)

\(\Rightarrow 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, 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, FUR2 2018 VCAA 4

Parcel deliveries are made between five nearby towns, `P` to `T`.

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 `P` to check all the roads and return to town `P` 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
  1. `2\ text(roads)`
  2. `108\ text(km)`
Show Worked Solution

a.   `text(Minimum distance if Eulerian circuit exists.)`

♦♦ Mean mark 31%.

`->\ text(no Eulerian circuit possible since 4 vertices are odd)`

`->\ text(if 2 edges added, Eulerian circuit exists)`

`:.\ text(Inspector will travel on 2 roads more than once.)`

 

b.   `text(By inspection, an extra edge added to)\ PQ\ text{(10)}`

♦♦♦ Mean mark 14%.

`text(and)\ ST\ text{(12) creates an Eulerian circuit with}`

`text(minimum distance.)`
 

`:.\ text(Min distance)`

`= (10 xx 2) + (12 xx 2) + 14 + 20 + 6 + 7 + 8 + 9`

`= 108\ text(km)`

NETWORKS, FUR2 2018 VCAA 2

In one area of the town of Zenith, a postal worker delivers mail to 10 houses labelled as vertices `A` to `J` 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 `F` and will continue her deliveries by following a Hamiltonian path from `F`.

     

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

 

Show Answers Only
  1. `text(Vertex)\ F`
  2. `2`
  3.  `text(See Worked Solutions)`
Show Worked Solution

a.   `text(Vertex)\ F`
 

b. `text(Eulerian trail)\ =>\ text(all edges used exactly once.)`

`text(6 vertices are odd)`

`=> 2\ text(extra edges could create graph with only 2)`

`text(odd vertices)`

`:.\ text(Minimum of 2 extra edges.)`
 

c.  `text{One example (of a number) beginning at)\ F:}`
 


 

`text{(Note: path should not return to}\ F text{)}`

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 2008 VCAA 5 MC

A connected planar graph has five vertices, `A`, `B`, `C`, `D` and `E`.

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  `v + f = e + 2`  could not be used.

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

Show Answers Only

`=> E`

Show Worked Solution

`text(Consider)\ E,`

♦ Mean mark 41%.

`text(If one edge added, the planar graph would)`

`text(have exactly 2 vertices that are odd, and an)`

`text(Eulerian path could exist.)`

`=> E`

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 9 MC

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

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 `Q` more than once.

•  The sum of the degrees of vertices `P` and `Q` 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.   `0`

B.   `1`

C.   `2`

D.   `3`

E.   `4`

Show Answers Only

`B`

Show Worked Solution

`text(“The path could have included vertex)\ Q`

♦♦ Mean mark 30%.

`text(more than once” is the only true statement.)`

`=>  B`

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.

     

    1. State a vertex at which Jamie could begin his walk.  (1 mark)
    2. 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 6-7 MC

Consider the following four graphs.
 


 

Part 1

How many of these four graphs have an Eulerian circuit?

A.  `0`

B.  `1`

C.  `2`

D.  `3`

E.  `4`

 

Part 2

How many of these four graphs are planar?

A.  `0`

B.  `1`

C.  `2`

D.  `3`

E.  `4`

Show Answers Only

`text(Part 1:)\ B`

`text(Part 2:)\ E`

Show Worked Solution

`text(Part 1)`

`text(An Euler circuit cannot exist if any vertices)`

`text(have an odd degree.)`

`=>  B` 

♦♦♦ 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.

 

`text(Part 2)`

`=>  E`

 

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 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, `A`, `B`, `C` and `D`.
 

NETWORKS, FUR2 2008 VCAA 21
 

  1. How many different ways may a vehicle travel from town `A` to town `D` 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 towns that do not pass through any other town.

    1. One more edge needs to be added to complete this network. Draw in this edge clearly on the diagram above.  (1 mark)
    2. With reference to the network diagram, explain why a motorist at `A` could not drive each of these routes once only and arrive back at `A`.  (1 mark)
Show Answers Only
  1. `7`
    1.  
      networks-fur2-2008-vcaa-2-answer
    2. `text(Driving each route once and arriving back at)\ A`

       

      `text(requires an Eulerian circuit where all vertices must)`

       

      `text(be an even degree.)`

       

      `text(The vertices at)\ C\ text(and)\ B\ text(are odd.)`

       

      `:.\ text(No Eulerian circuit exists.)`

Show Worked Solution

a.   `text(Let the two unnamed intersections be)\ T_1\ text{(top) and}\ T_2.`

`text(The possible paths are:)`

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

`ACD, ACT_2BD, ACT_2T_1BD, AT_1T_2CD,`

`AT_1T_2BD, AT_1BD, AT_1,BT_2CD.`

`:. 7\ text(different ways from)\ A\ text(to)\ D.`

 

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

 

b.ii.   `text(Driving each route once and arriving back at)`

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

   `A\ text(requires an Eulerian circuit where all)`

   `text(vertices must be an even degree.)`

   `text(The vertices at)\ C\ text(and)\ B\ text(are odd.)`

   `:.\ text(No Eulerian circuit exists.)`

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. At which landmark must he finish his journey?  (1 mark)
    2. 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`. 

       

      Write down the order Cathy will visit the landmarks.  (1 mark)

    2. Suppose Cathy starts at `S`, then visits `R` but does not finish at `T`. 

       

      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 3

The following network diagram shows the distances, in kilometres, along the roads that connect six intersections `A`, `B`, `C`, `D`, `E` and `F`.
 

  1. If a cyclist started at intersection `B` 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 `A`.

     

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

     

    1. Apart from intersection `A`, through which intersections does the blue team pass more than once?  (1 mark)
    2. How many kilometres does the blue team cycle?  (1 mark)
  3. 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
  1. `D`
    1. `B, D\ text(and)\ F`
    2. `32\ text(km)`
  3. `B\ text(and)\ D`
Show Worked Solution

a.   `D`

 

b.i.   `text(Consider the path)`

`AFDEFBCDFBA`

`:.\ text(Passes through)\ B, D,\ text(and)\ F\ text(more)`

`text(than once.)`

 

b.ii.   `text{Total distance (Blue)}`

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

`= 32\ text(km)`

 

c.   `text(An Euler circuit can only exist when the)`

`text(degree of all vertices is even.)`

`:.\ text(The bush track joins)\ B\ text(and)\ D.`

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.

     

     

    1. At which picnic area will the park ranger finish?  (1 mark)
    2. What mathematical term is used to describe the route the park ranger takes?  (1 mark)
  4. 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)`
    1. `P4`
    2. `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. Write down the names of the towns at the start and at the end of Charlie’s path.  (1 mark)
    2. 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. `text(Bower, Eden)`
    2. `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 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.

       

      A journey starts and finishes at the house and travels along every edge in the network.

       

      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
       

    2. What is the mathematical term that is used to describe this minimum length of pipe in part i.?  (1 mark)
Show Answers Only
    1. `160\ text(m)`
    2. `2`
    3. `1250\ text(m)`
    1.  
      NETWORKS, FUR2 2012 VCAA 1 Answer
    2. `text(Minimal spanning tree)`
Show Worked Solution

a.i.   `text(Shortest distance)`

`=70 + 90`

`= 160\ text(m)`

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

 

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

 

a.iii.   `text{An Eulerian path is possible if it starts at}`

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

   `text{the house (odd vertex) and ends at the top}`

   `text{right vertex (the other odd vertex). However,}`

   `text{70 metres must be added to return to the}`

   `text{house.}`

`:.\ text(Total distance)` `= 1180 + 70`
  `= 1250\ text(m)`

 

b.i.    NETWORKS, FUR2 2012 VCAA 1 Answer

 

b.ii.   `text(Minimal spanning tree)`