Question1

(a)The connected planar graph G has degree sequence

(g1, g2, g3, g4, g5, g6),

And the connected planar graph H has degree sequence

(2, g1, g2, g3, g4, g5, g6).

If G has f faces and m edges, find expressions for the number of faces

FH and edges mH of H in terms of f and m.

(b)The non-planar graph G has degree sequence

(2, 2, 3, 3, 3, 3, 4, 4).

(i)Explain why G cannot contain a subdivision of K5, but must contain a subdivision of K3,3

(ii) Draw two such a graphs, one in which K3,3 is a subgraph, and One in which there is a proper subdivision of K3,3 as a subgraph .

(c) Let G be the following graph.

(i)Write down a Hamiltonian cycle in G. Then, using the cycle method, prove that G is not planar.

(ii) Use a corollary of Euler's formula to give an alternative proof that G is not planar.

(d)A school wants to schedule six sports events (badminton, cricket, football, gymnastics, swimming and tennis), but is constrained because six of the participants are involved with more than one sport, as follows.

 Ann swimming, badminton, tennis

Ben badminton, football

Cerri swimming, gymnastics, cricket

David football, tennis

Edgar football, cricket

Finn swimming, football

One of the organisers suggests that three different time slots will be sufficient because no

participant is involved with more than three different sports.

Find the chromatic number of a suitable subgraph of K6, and use it to explain why this suggestion is incorrect

Question 2

A mobile sawmill is used in the Dartmoor woodlands

Auswell, Boro, Chase, Dendles and Erme,

Producing 4,6,7,5 and 3 cubic metres of planked hardwood at each, respectively.

Five local joinery workshops J1, J2, J3, J4 andJ5 each require 5 cubic metres of such wood. The costs of transportation, in pounds per cubic metre, from each woodland (represented by its initial letter) to each joinery workshop are given in the following cost matrix.

 (a)(i) Use the Hungarian algorithm for the transportation problem to find the first revised cost matrix and the first partial graph.

(ii) An initial maximum flow is

AJ3:4 ;BJ1:5; BJ2:1; CJ2:4 ;CJ3:1 ;DJ5:5 ;EJ4:3.

Use this initial maximum flow, and continue to apply the algorithm to find the minimum cost flow pattern and show that it has a cost of £119. Note that to obtain the marks, you should follow the algorithm precisely.

(b) Consider now that Boro Woods actually produces 9 cubic metres of Planked hardwood.

(i)Write down a cost matrix and a complete bipartite graph with Supplies and demands that models this new problem, and find the first revised cost matrix and first partial graph.

(ii) Without completing the algorithm, explain how the flow pattern resulting from the application of the algorithm is used to give a solution to the problem.

(iii) Will the cost £119 be an upper or lower bound for this new problem? Briefly explain your answer.

You should be able to answer Question 3 after you have studied Design 3.

Question 3

(a) Consider the following code A of length 4:

{0000, 1110, 1011, 0101}.

(i)Is code A cyclic? Justify your answer briefly.

(ii) Write down the minimum distance δ of A, and find the number of errors that can be detected and corrected by A.

(iii) Find a parity check matrix for code A.

(iv) The two words1 10 1and 11 11 are received over a noisy channel.

Attempt to decode these two words, first by nearest neighbour decoding, then by finding their error syndrome. Explain how your results relate to a particular feature of the parity check matrix.

(v) Find all the code words of the dual code A∗.

(vi) Are the codes A and A∗ equivalent? Justify your answer briefly.

(b)The following characters are associated with message words that are Binary representations of the numbers 0 to7, respectively:

'A', 'E', 'F', 'I', 'L', 'N', 'Y', '!'.

(That is, the character 'A' is associated with the message word 000, the character 'E' with the message word 00 1, and so on.)

(i)Encode each of the message words using the (7, 3) simplex code With the following generator matrix (in standard form):

Display your answer in a table with columns headed 'Character', 'Message word' and 'Code word'.

(ii) A message of 8 characters encoded as above is sent through a noisy channel, and the following words (listed in order horizontally)are received.

0100111 0011000 1010101 0100000

0001110 1001110 1101001 0110010

Some of the received (encoded) words contain one or two errors.

Decode the message either by comparing the received words with your table from part (b)(i), or by use of a parity check matrix and error syndromes. Therefore identify the received words that Contain errors, and correct them where possible.

Use the redundancy of the English language to guess the intended plain-text message