SmarterEd

Aussie Maths & Science Teachers: Save your time with SmarterEd

Networks, SMB-015 MC

Consider the following four statements about the graph above:

    • The graph is planar.
    • The graph contains a cycle.
    • The graph is connected.
    • The graph contains an Eulerian trail.

How many of these statements are true?

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

`C`

Show Worked Solution

`text{Consider each statement:}`

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

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

`text{Graph is connected}\ -> \text{a path exists to connect any}`

`text{two vertices (True)}`

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

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

`=> C`

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-008

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 trail through this network of train lines.

  1. Write down the names of the towns at the start and at the end of Charlie’s trail.  (1 mark)
  2. What distance did he travel?  (2 marks)
Show Answers Only
  1. `text(Bower, Eden)`
  2. `910\ text(km)`
Show Worked Solution

i.   `text{Eulerian trail starts and ends at odd degree vertices (towns).}`

`text(Bower, Eden or Eden, Bower)`

 
ii.   `text{Eulerian trail}\ =>\ text{every edge used once only.}`

`text{Distance}\ (BDABCDEACE)`

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

`= 910\ text(km)`

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

Networks, SMB-003

The following network diagram has a Eulerian trail. 
 

Starting at vertex `D`, describe one Eulerian trail and at what vertex the trail finishes.  (2 marks)

Show Answers Only

`text{Possible trails:}`

`DACEBD, DBECAD`

`text{All Eulerian trails will finish at vertex}\ D.`

Show Worked Solution

`text{Possible trails:}`

`DACEBD, DBECAD`

`text{All Eulerian trails will finish at vertex}\ D.`

Networks, SMB-002

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

  1. A cyclist started at intersection `D` and cycled along every road in this network once only. What route would the cyclist take and at which intersection would she finish?  (3 marks)

  2. What is another name for this type of trail?   (1 mark)

Show Answers Only

i.   `text{Possible trails:}`

`DEFDCBFAB, DEFDCBAFB,`

`DEFBAFDCB, DEFABFDCB`

`text{All routes finish at intersection}\ B.`
 

ii.   `text{Eulerian trail}`

Show Worked Solution

i.   `text{Possible trails:}`

`DEFDCBFAB, DEFDCBAFB,`

`DEFBAFDCB, DEFABFDCB`

`text{All routes finish at intersection}\ B.`
 

ii.   `text{Eulerian trail}`

Networks, SMB-001

The network diagram below describes 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, and cannot be used by skateboards.

  1. Describe a path that a skateboarder at ramp `V` could use to travel to ramp `T` that uses 4 edges only.   (1 mark)

  2. A skateboarder begins skating at ramp `W` and follows an Eulerian trail.
  3. What trail does the skateboarder take?  (2 marks)

Show Answers Only
  1. `text{Possible paths:}\ \ VZYT, VZUT`
  2. `XYZWVZUYTU\ \ \text{(Finishes at ramp}\ U\text{)}`
Show Worked Solution

i.    `text{Possible paths:}\ \ VZYT, VZUT, VZYUT`

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

`XYZWVZUYTU`