Ask Math Expert


Home >> Math

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.

2467_Connected planar graph.png

(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.

596_Connected planar graph1.png

 (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):

898_Connected planar graph2.png

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

Math, Academics

  • Category:- Math
  • Reference No.:- M9750009

Have any Question?


Related Questions in Math

Questions -q1 prove the following identitiesa sinx y sinx

Questions - Q1. Prove the following identities a. sin(x + y) + sin(x - y) = 2 sin x cos y b. sec(x - y) = cos(x + y)/(cos 2 x - sin 2 y) c. tan 2 x - sin 2 x = (tan x sin x) 2 Q2. Solve the following equations for x ∈ [0 ...

Maths assignment - 1 analysis of a data setusing a

Maths Assignment - 1. Analysis of a data set Using a continuous data set you are requested to collect in the types of data and gathering data section, perform a statistical analysis on your data. You have opportunities t ...

Questions - provide solution to the following questionsq1

Questions - Provide solution to the following questions: Q1. Evaluate the following: ∫xsin3xdx Q2. If , then for what value of α is A an identity matrix? Q3. The line y = mx + 1 is a tangent to the curve y 2 = 4x. Find t ...

Assessment taskpractical investigation- question 1 requires

Assessment Task Practical Investigation - Question 1 requires selecting reference points from the graph. It is expected that each student will choose different reference points to other students. Take note of the criteri ...

1 suppose that n 10088821 is a product of two distinct

1. Suppose that n = 10088821 is a product of two distinct primes, and Φ(n) = 10082272. Determine the prime factors of n. 2. It is easy to show that the converse of Fermat's Theorem does not hold; i.e., the congruence a n ...

Assignment -question 1 let t and or 0 1 be a boolean

Assignment - Question 1. Let (T, ∧, ∨,', 0, 1) be a Boolean Algebra. Define ∗ : T × T → T and o : T × T → T as follows: x ∗ y := (x ∨ y)' x o y := (x ∧ y)' (a) Show, using the laws of Boolean Algebra, how to define x ∗ y ...

Assignment - provide solution to the following questionsq1

Assignment - Provide solution to the following questions: Q1. Evaluate the following: ∫xsin3x dx Q2. If , then for what value of α is A an identity matrix? Q3. The line y = mx + 1 is a tangent to the curve y 2 = 4x. Find ...

Question 1 what is the nth order approximation using taylor

Question: 1. What is the nth order approximation using Taylor series? 2. What is Error Propagation? 3. Please explain what the total numerical error is? Please illustrate how the change of step size will affect the total ...

Mathematics- algebraic geometry problemlet k denotes an

Mathematics- Algebraic Geometry Problem Let K denotes an algebraically closed field and let P 1 be constructed as in Example 5.5(a) in Gathmanns notes, i.e. P 1 is the gluing of X 1 = A 1 and X 2 = A 1 along  the open su ...

Mathematics- algebraic geometry problemlet k denotes an

Mathematics- Algebraic Geometry Problem Let K denotes an algebraically closed field and let P 1 be constructed as in Example 5.5(a) in Gathmanns notes, i.e. P 1 is the gluing of X 1 = A 1 and X 2 = A 1 along  the open su ...

  • 4,153,160 Questions Asked
  • 13,132 Experts
  • 2,558,936 Questions Answered

Ask Experts for help!!

Looking for Assignment Help?

Start excelling in your Courses, Get help with Assignment

Write us your full requirement for evaluation and you will receive response within 20 minutes turnaround time.

Ask Now Help with Problems, Get a Best Answer

Why might a bank avoid the use of interest rate swaps even

Why might a bank avoid the use of interest rate swaps, even when the institution is exposed to significant interest rate

Describe the difference between zero coupon bonds and

Describe the difference between zero coupon bonds and coupon bonds. Under what conditions will a coupon bond sell at a p

Compute the present value of an annuity of 880 per year

Compute the present value of an annuity of $ 880 per year for 16 years, given a discount rate of 6 percent per annum. As

Compute the present value of an 1150 payment made in ten

Compute the present value of an $1,150 payment made in ten years when the discount rate is 12 percent. (Do not round int

Compute the present value of an annuity of 699 per year

Compute the present value of an annuity of $ 699 per year for 19 years, given a discount rate of 6 percent per annum. As