(a) Explain the difference between an Euler path and an Euler cycle. (b) Find the maximum...

 

Transcribed Image Text:

(a) Explain the difference between an Euler path and an Euler cycle. (b) Find the maximum number of comparisons to be made to find any record in a binary search tree which holds 3000 records. [3] (c) Explain what is meant by the term 'path'. (d) The figure shows a network of cycle tracks. The number on each edge represents the length, in miles, of that track. Jay wishes to cycle from A to I as part of a cycling holiday. She wishes to minimise the distance she travels. SP R 2 44 21 15 27 44 21 B Use Dijkstra's algorithm to find the shortest path from A to I. Show your working. [3] [6] (e) Given S' is the set of integers (2,3,4,5,6,7,8). Let R be a relation defined on S by the following condition such that, Va, y € S.xRyzmod 2 = y mod 2 i. Draw the digraph of R. ii. Show that R is an equivalence relation. iii. Find the equivalence classes for R item is R a partial order? Explain your answer (f) Letf: A B and g: B C be functions. Prove that if g of is one-to-one, then f is one-to-one. [2] [6] [2] [2] [6] (a) Explain the difference between an Euler path and an Euler cycle. (b) Find the maximum number of comparisons to be made to find any record in a binary search tree which holds 3000 records. [3] (c) Explain what is meant by the term 'path'. (d) The figure shows a network of cycle tracks. The number on each edge represents the length, in miles, of that track. Jay wishes to cycle from A to I as part of a cycling holiday. She wishes to minimise the distance she travels. SP R 2 44 21 15 27 44 21 B Use Dijkstra's algorithm to find the shortest path from A to I. Show your working. [3] [6] (e) Given S' is the set of integers (2,3,4,5,6,7,8). Let R be a relation defined on S by the following condition such that, Va, y € S.xRyzmod 2 = y mod 2 i. Draw the digraph of R. ii. Show that R is an equivalence relation. iii. Find the equivalence classes for R item is R a partial order? Explain your answer (f) Letf: A B and g: B C be functions. Prove that if g of is one-to-one, then f is one-to-one. [2] [6] [2] [2] [6]

Answer rating: 100% (QA)

a An Euler path is a path that visits every edge of a graph exactly once An Euler cycle also known as an Eulerian circuit is a path that visits every vertex of a graph exactly once and ends at the sta... View the full answer