SmarterEd

Aussie Maths & Science Teachers: Save your time with SmarterEd

Networks, SMB-012

A network diagram is drawn below.
 

  1. Starting at vertex `Z`, identify a trail that uses 6 edges and ends at vertex `V`.   (1 mark)

  2. Starting at vertex `V`, identify all six different paths that end at vertex `Y`.   (2 marks)

  3. Is the route identified as `YXUVXY` a circuit? Explain.  (1 mark)

Show Answers Only

i.    `text{Trail: repeated vertices permitted but no repeated edges}`

`text{Trail (6 edges)}\ Z–V:`

`ZWXYUXV\ \ \text{or}\ \ ZWXUYXV` 
 

ii.    `text{Path: a route that does not repeat vertices or edges.}`

`text{Possible paths}\ V–Y:`

`VUY, VUXY, VUXWZY`

`VXUY, VXY, VXWZY`
 

iii.   `text{Circuit: starts and ends at the same vertex with repeated}`

`text{vertices allowed but no repeated edges.}`

`YXUVXY\ \text{is not a circuit because it edge}\ XY\ \text{is repeated.}`

Show Worked Solution

i.    `text{Trail: repeated vertices permitted but no repeated edges}`

`text{Trail (6 edges)}\ Z–V:`

`ZWXYUXV\ \ \text{or}\ \ ZWXUYXV`
 

ii.    `text{Path: a route that does not repeat vertices or edges.}`

`text{Possible paths}\ V–Y:`

`VUY, VUXY, VUXWZY`

`VXUY, VXY, VXWZY`
 

iii.   `text{Circuit: starts and ends at the same vertex with repeated}`

`text{vertices allowed but no repeated edges.}`

`YXUVXY\ \text{is not a circuit because it edge}\ XY\ \text{is repeated.}`

Networks, SMB-011

A network diagram is drawn below.
 

  1. Starting at vertex `Q`, identify all five different paths that end at vertex `S`.   (2 marks)

  2. Starting at vertex `P`, identify four different cycles that exist in the network.   (2 marks)

  3. Starting at vertex `P`, what is the total number of cycles that exist in the network.  (1 mark)

Show Answers Only

i.    `text{Paths from}\ Q–S:`

`QS, QRS, QRPS, QPRS, QPS`
 

ii.    `text{Cycle: a path that ends at the same vertex without}`

`text{repeating any vertices.}`

`text{Possible cycles (any 4 from the following):}`

`PQRP, PQSRP, PQRSP, PQSP, PSRP`

`PSRQP, PSQRP, PSQP`
 

iii.  `8\ \text{(see listed in part (ii))}`

Show Worked Solution

i.    `text{Paths from}\ Q–S:`

`QS, QRS, QRPS, QPRS, QPS`
 

ii.    `text{Cycle: a path that ends at the same vertex without}`

`text{repeating any vertices.}`

`text{Possible cycles (any 4 from the following):}`

`PQRP, PQSRP, PQRSP, PQSP, PSRP`

`PSRQP, PSQRP, PSQP`
 

iii.  `8\ \text{(see listed in part (ii))}`

Networks, SMB-010

  1. Starting at vertex `A`, identify all the different paths that finish at vertex `D`, using only three edges.   (2 marks)

  2. Starting at vertex `A`, identify a cycle route?   (1 mark)

  3. Explain the difference between a cycle and a circuit route.   (1 mark)

Show Answers Only

i.    `text{Three edge paths from}\ A–D:`

`ACED, ABCD, ABED, AECD`

ii.    `text{Cycle: a path that ends at the same vertex without}`

`text{repeating any.}`

`text{Possible cycles (many examples exist in this network):}`

`ABEA, ABCEA, ACBA, …`

iii.  `text{A circuit is a path that begins and ends at the same vertex.}`

`text{A cycle begins and ends at the same vertex, without}`

`text{repeating any vertices.}`

Show Worked Solution

i.    `text{Three edge paths from}\ A–D:`

`ACED, ABCD, ABED, AECD`
 

ii.    `text{Cycle: a path that ends at the same vertex without}`

`text{repeating any.}`

`text{Possible cycles (many examples exist in this network):}`

`ABEA, ABCEA, ACBA, …`
 

iii.  `text{A circuit is a path that begins and ends at the same vertex.}`

`text{A cycle begins and ends at the same vertex, without}`

`text{repeating any vertices.}`

Networks, SMB-005

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)

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?  (2 marks)

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

Show Answers Only
  1. `3`
  2. `1000\ text(m)`
  3. `P4`
  4. `text(Euler trail)`
Show Worked Solution

i.   `3`
 

ii.   `text( Shortest distance)`

`= E-P1-P3`

`= 600 + 400`

`= 1000\ text(m)`
 

iii.   `text(A route could be)`

`E − P1 − P2 − P3 − P4 − P5`

`− E − P6 − P1 − P3 − P6 − P4`

`:.\ text(Finish at)\ P4`

`text{(Konigsberg bridge – Eulerian trail ends at the only other}`

`text{odd degree vertex)}`
 

iv.   `text(Eulerian trail)`

Networks, SMB-004

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 paths 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?  (2 marks)

Show Answers Only
  1. `200\ text(km)`
  2. `6`
  3. `text(Bredon)`
Show Worked Solution

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

`= 60 + 140`

`= 200\ text(km)`

 

ii.   `text{Paths are walks where vertices and edges are only used once.}`

`text(Different paths are:)`

`FDC, FEDC, FEBC, FEABC, FDEBC, FDEABC`

`:. 6\ text(different ways)`

 

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

`text{at Bredon.}`

`text{Note: solving this can be done quickly by applying the}`

`text{concept underlying the Konigsberg Bridge problem}`

`text{(i.e. it finishes at the only other odd-degree vertex)}`