SmarterEd

Aussie Maths & Science Teachers: Save your time with SmarterEd

Networks, SMB-014 MC

An Eulerian trail for the graph above will be possible if only one edge is removed.

In how many different ways could this be done?

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

`D`

Show Worked Solution

`text{Konigsberg: an Eulerian trail needs two vertices (only) to have}`

`text{an odd degree.}`

`text{The graph has 4 vertices that are odd degree.}`

`text{Removing any of the dashed edges below would achieve this.}`
 

`=> D`

Networks, SMB-013 MC

Consider the graph below.

The minimum number of extra edges that are required so that an Eulerian trail is possible in this graph is

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

`B`

Show Worked Solution

`\text{Eulerian trail – every edge is used once only.}`
 

`text{Eulerian trails allow two vertices (only) to be odd.}`

`:.\ text{Need 1 extra edge that creates two even degree vertices (see image).}`

`=>  B`

Networks, SMB-007

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

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

Show Answers Only
  1. `4`
  2. `P\ text{(the other odd degree vertex)}`
  3. `5`
Show Worked Solution

i.   `4`
 

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

`text{(The Konigsberg Bridge concept is used here)}`
 

iii.   `text{Any vertex (landmark) with a degree of 3 or 4 will be seen twice.}`

`5 (N, T, R, P, U)`

Networks, SMB-006

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, giving reasons.  (2 marks)

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

i.    `text(Vertex)\ F`
 

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

`text(6 vertices are odd)`

`text{Konigsberg Bridge concept: Eulerian trail can exist if 2 vertices (only) are odd}`

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

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

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)}`