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.

In kilometres, what is the shortest distance between Farnham and Carrie? (1 mark)

--- 1 WORK AREA LINES (style=lined) ---
How many different paths are there to travel from Farnham to Carrie without passing through any town more than once? (1 mark)

--- 2 WORK AREA LINES (style=lined) ---

An engineer plans to inspect all of the roads in this network.

He will start at Dunlop and inspect each road only once.

At which town will the inspection finish? (2 marks)

--- 3 WORK AREA LINES (style=lined) ---

Show Answers Only

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