Final Examination
MATH2302 Discrete Mathematics II
离散数学代考 a) (1 mark) Is 19 related to 30 in this poset? Justify your answer. b) (1 mark) Is 14 related to 18 in this poset? Justify your answer.
a) (1 mark) Is 19 related to 30 in this poset? Justify your answer.
b) (1 mark) Is 14 related to 18 in this poset? Justify your answer.
c) (4 marks) Determine the minimum number of chains of this poset into which S can be partitioned, and justify your answer.
3.(6 marks) 离散数学代考
For each integer n ≥ 0, let unbe the number of arrangements of n objects chosen from {a, b} where:
- a must be chosen an even number of times; and
- b must be chosen at least once.
Use generating functions to determine a formula for un in terms of n.
4.(6 marks)
Use generating functions to find a closed form solution for the sequence defined recursively as
a0 = 1, a1 = 5, ai+2 = 7ai+1 − 12ai for each integer i ≥ 0.
5.(4 marks) 离散数学代考
Determine all the self-conjugate partitions of 8. (Note that in addition to listing the partitions, you need to justify that you have found all of them.)
6.
a) (4 marks) Demonstrate how Theorem 25.76 can be used to verify that the sequence 6, 4, 4, 3, 3, 3, 3, 2, 2 is graphical, showing full details at each step. Then draw the corresponding graph G.
b) (2 marks) Assume G is a graph which has degree sequence 6, 4, 4, 3, 3, 3, 3, 2, How many edges must be removed from G to produce a spanning tree? Draw one such spanning tree for the graph G as constructed in Part a).
7. 离散数学代考
a) (2 marks) Show that it is possible to 3-colour (colours red, blue and green) the edges of the graph K7, so that the edges of each colour form a Hamilton cycle in K7.
b) (2 marks) Draw a graph G on 6 vertices which contains a Hamilton cycle but not a semiEulerian trail. Justify your answer.
c) (2 marks) Prove that the complete bipartite graph K8,9does not contain a Hamilton cycle.
8.(6 marks)
Use either Kruskal’s or Prim’s Algorithm to find a minimum weighted spanning tree in the weighted graph given below. State which algorithm you have used, draw the spanning tree and give the minimum total weight. You must show each step of the algorithm you haveimplemented.
9.
a) (3 marks) Prove that if graph G = (V,E), where |V | ≥ 2, has chromatic number at most 2, then it is bipartite.
b) (3 marks) Suppose that r is an odd integer. Prove that if G = (V,E) is an r regular graph then |V | = 2m, for some integer m.
10. 离散数学代考
a) (3 marks) Consider the word abcdc−1b−1a−1d−1.
i) Draw the polygon that is represented by this word.
ii) Compute the Euler characteristic and orientability of thecorresponding surface.
iii) Name the surface that this word represents.
b) (3 marks) What surface is represented by the worda1a2…an−1ananan−1 …a2a1 (for any n ≥ 1)? You should give your answer in terms of n.
11. 离散数学代考
A simple closed curve on a surface is a path through the surface that starts and ends at the same point, but does not touch itself at any other points (in other words, a loop with no selfintersections).
a) (3 marks) Describe how to find a simple closed curve c on the projective plane with the property that, if you cut the surface open along c, the resulting surface will be connected and orientable. (Note that the resulting surface will also have boundary.)
b) (5 marks) Prove that every closed non-orientable surface contains a simple closed curve c with the property that, if you cut the surface open along c, the resulting surface will be connected and orientable.
12.
a) (3 marks) Let (V,B) be a Steiner triple system, where |V | = v. Prove that v ≡1 or 3(mod 6).
b) (3 marks) Let (V,B) be a Steiner triple system, where |V | = v. Let x ∈ V . Write down a formula for the number of blocks containing point x and justify your answer.
更多代写：软件工程专业课业代写 gre保分 英国哲学final quiz代考 营销代写essay 犹他大学论文代写 代上网课价格
