辅导MATH2069/2969辅导asp语言程序

MATH2069/2969 Semester 1 Main,

SECTION A: Discrete Mathematics 

Use separate writing booklets for sections A and B. 

1. A group of 30 people get together to start a small company. 

(a) How many different ways can they elect a managing committee of 8 people, 

including 2 people appointed as co-presidents? 

(b) 100 indistinguishable cards are printed with the company name and logo. 

What is the number of ways to distribute the cards among the 30 employees, 

given that everyone must have at least 2 cards? 

(c) In their new building, there are 10 offices, so exactly 3 people will be assigned 

to each office. How many ways are there to assign an office to each employee? 

(d) There are 5 priority projects that the company needs to work on. How many 

ways are there to assign an employee to each task, so that each task has at 

least one person working on it? 

2. (a) Write the characteristic polynomial of the recurrence relation 

bn = bn−1 + 12 bn−2, where n > 2. 

(b) Find the general solution of the recurrence relation 

bn = bn−1 + 12 bn−2, where n > 2. 

(c) Find one particular solution of the recurrence relation 

an = an−1 + 12 an−2 − 4 

n, where n > 2. 

(d) Find the solution of the recurrence relation 

an = an−1 + 12 an−2 − 4 

n, where n > 2, 

satisfying the initial conditions a0 = 0 and a1 = −2. 

turn to page 3 

MATH2069/2969 Semester 1 Main, 2019 page 3 of 6 

3. This question is for MATH2069 students only. 

MATH2069/2969 Semester 1 Main, 2019 page 4 of 6 

SECTION B: Graph Theory 

Use separate writing booklets for sections A and B. 

4. (a) Only one of the sequences (3, 3, 3, 3, 4, 5), (3, 3, 4, 4, 4, 6), and (3, 3, 3, 3, 4, 4) 

is graphic. Explain why two of these sequences are not graphic. 

(b) Draw a picture of a graph whose degree sequence coincides with the remain- 

ing sequence in part (a). 

(c) Either write down an Eulerian trail in the following graph, or explain why 

none exists. a b 

5. (a) Complete the formulation of the Travelling Salesman Problem: “Given a 

connected weighted graph, find a walk which . . . ”. 

(b) Find a walk which solves the Travelling Salesman Problem for the following 

weighted graph. Justify your answer. 

(c) Find a minimal spanning tree for the weighted graph in (b). 

(d) Consider the trees with 7 vertices {1, 2, 3, 4, 5, 6, 7} which have a vertex of 

degree 4. 

(i) What is the possible number of leaves in such a tree? 

(ii) What is the number of isomorphism classes of such trees? 

Justify your answer to each of the questions. 

(e) A tree has two vertices of degree 4. What is the minimum possible number 

of vertices in such a tree? Justify your answer. 

turn to page 5 

MATH2069/2969 Semester 1 Main, 2019 page 5 of 6 

6. This question is for MATH2069 students only. 

(a) Let t be a natural number. Define what is meant for a graph G to be t- 

colourable. 

(b) Use mathematical induction on the number n of vertices in G to show that 

any graph G is t-colourable for t = ∆(G) + 1. 

(c) The graph H is given by the picture 

(i) What is the maximum possible value of the chromatic number χ(H) 

as provided by the Brooks Theorem? 

(ii) What is the exact value of χ(H)? Justify your answer. 

(iii) What are the possible values of the edge chromatic number χ′(H) as 

provided by the Vizing Theorem? 

(iv) What is the exact value of χ′(H)? Justify your answer. 

6. This question is for MATH2969 students only. 

(a) For any n > 6 the graph Gn can be drawn as a regular polygon with n 

vertices together with all diagonals of the minimal length. 

[ For instance, the picture above on this page represents Gn for n = 6 ]. 

(i) Calculate the chromatic numbers χ(Gn). Justify your answer. 

(ii) Calculate the edge chromatic number χ′(G8). Justify your answer. 

(iii) Prove that if n is odd then χ′(Gn) = 5. 

(b) Find the chromatic polynomial for the graph 

turn to page 6 

MATH2069/2969 Semester 1 Main, 2019 page 6 of 6 

This is the end of the examination paper.