关键词 > MATH2302/7308
MATH2302/7308 Assignment 4 2022
发布时间：2022-10-21
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
MATH2302/7308
Assignment 4
2022
This Assignment is compulsory, and contributes 10% towards your final grade in MATH2302 or MATH7308. It should be submitted by 2pm on Monday 24 October, 2022. In the absence of a valid excuse, assignments submitted after the due date will not be marked. (See the ECP for how to request an extension.) You should submit your assignment electronically.
Prepare your assignment as a PDF file, either by typing it or by scanning your handwritten work. Ensure that your name, student number and tutorial group number appear on the first page of your submission. Check that your PDF file is legible and that the file size is not excessive. Files that are poorly scanned and/or illegible may not be marked. Upload your submission using the assignment submission link in Blackboard.
1. (6 marks) Consider the graph G drawn below, with three of the edges labelled x, y and z . Prove that any perfect matching in G must contain at least one of the edges x, y , z .
x
2. (10 marks total) Let G be the graph drawn below.
(a) (2 marks) Write down a maximum size clique in G and state the clique number ω(G). No
justification is required.
(b) (3 marks) Determine the domination number σ(G). Justify your answer.
(c) (1 mark) Give a minimal dominating set of size σ(G)+1 which is also a maximal independent set. No justification is required.
(d) (1 mark) Give a minimal dominating set of size σ(G)+1 which is not a maximal independent set. No justification is required.
(e) (3 marks) Determine the edge chromatic number χ\ (G). Justify your answer.
a
h
d c
3. (10 marks total) For any even integer n ≥ 4, let G be the graph constructed as follows. The vertices correspond to 2-element subsets of the set P = {1, 2, . . . , n}. Two vertices are adjacent if and only if the corresponding sets have a common element. Determine each of the following and justify your answers.
(a) β(G) (5 marks)
(b) χ(G) (5 marks) (hint: consider edge colourings of Kn )
4. (8 marks) Use Dijkstra’s algorithm to determine the distance from A to each other vertex in the weighted graph shown below, and state a shortest path from A to C .
A
D 6 C
5. (6 marks) Consider the weighted graph shown in Question 4. Find a minimum weight spanning tree of this graph using either Prim’s Algorithm or Kruskal’s Algorithm. State which algorithm you are using, and show your working by listing edges and associated weights in the order added (no further explanation is required). Clearly state the weight of the spanning tree.
