[ Pobierz całość w formacie PDF ]
SECTION D
Discrete mathematics
1. [Maximum mark: 14]
The weights of the edges in a simple graph G are given in the following table.
Vertices A B C D E F
A - 4 6 16 15 17
B 4 - 5 17 9 16
C 6 5 - 15 8 14
D 16 17 15 - 15 7
E 15 9 8 15 - 18
F 17 16 14 7 18 -
(a) Use Prim s Algorithm, starting with vertex F, to find and draw the minimum
spanning tree for G. Your solution should indicate the order in which the edges
are introduced. [12 marks]
(b) Use your tree to find an upper bound for the travelling salesman problem for G. [2 marks]
2. [Maximum mark: 16]
(a) Use the Euclidean algorithm to find the greatest common divisor of 43 and 73. [5 marks]
Consider the equation 43x + 73y = 7 , where x, y"¢ð .
(b) (i) Find the general solution of this equation.
(ii) Find the solution which minimises | x| + | y|. [11 marks]
2207-7206 Turn over
10 M07/5/MATHL/HP3/ENG/TZ1/XX
3. [Maximum mark: 13]
Let H be the weighted graph drawn below.
(a) (i) Name the two vertices of odd degree.
(ii) State the shortest path between these two vertices.
(iii) Using the route inspection algorithm, or otherwise, find a walk, starting
and ending at A, of minimum total weight which includes every edge at
least once.
(iv) Calculate the weight of this walk. [11 marks]
(b) Write down a Hamiltonian cycle in H. [2 marks]
4. [Maximum mark: 9]
Consider the equation x12+1 = 7 y , where x, y "¢ð+ .
Using Fermat s little theorem, show that this equation has no solution. [9 marks]
5. [Maximum mark: 8]
Let K be a simple graph.
2
K
(a) Define the complement, , of K. [1 mark]
2
K
(b) Given that K has six vertices, show that K and cannot both contain an Eulerian
trail. [7 marks]
2207-7206
[ Pobierz całość w formacie PDF ]