Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit


School of Mathematics and Statistics

MAST20018 Discrete Maths and Operations Research


Permitted Materials

This exam and/or an offline electronic PDF reader, blank loose-leaf paper and a Casio FX-82 calculator.

One double sided A4 page of notes (handwritten or printed).

No headphones or earphones are permitted.


Instructions to Students

Wave your hand right in front of your webcam if you wish to communicate with the supervisor at any time (before, during or after the exam).

You must not be out of webcam view at any time without supervisor permission.

You must not write your answers on an iPad or other electronic device.

Off-line PDF readers (i) must have the screen visible in Zoom; (ii) must only be used to read exam questions (do not acess other software or files); (iii) must be set in flight mode or have both internet and Bluetooth disabled as soon as the exam paper is downloaded.

Writing

IMPORTANT NOTE (PLEASE READ): This assignment is being presented with the cover page you will see in the exam. Please get used to it and ignore the instructions regarding zoom for this assignment.

Write your answers on A4 paper. Page 1 should only have your student number, the subject code and the subject name. Write on one side of each sheet only. Each question should be on a new page. The question number must be written at the top of each page.

Scanning and Submitting

You must not leave Zoom supervision to scan your exam. Put the pages in question order and all the same way up. Use a scanning app to scan all pages to PDF. Scan directly from above. Crop pages to A4.

Submit your scanned exam as a single PDF file and carefully review the submission in Gradescope. Scan agin and resubmit if necessary. Do not leave Zoom supervision until you have confirmed orally with the supervisor that you have received the Gradescope confirmation email.

You must not submit or resubmit after having left Zoom supervision.


Question 1 Consider the following labelled graph:

(a) State an upper-bound and a lower-bound on the vertex-chromatic number of the graph, and give reasons for your answers.

(b) Find an optimal colouring of the graph.

(c) Classify the graph according to the following graph classes: trees, bipartite graphs, interval graphs, chordal graphs. Provide a reason for each answer.

(d) Beginning with the matching M = {(j,k)}, extend M into a maximum matching by repeatedly finding augmenting paths. At each step you should increase the number of edges in the matching by one and clearly indicate the original matching, the exposed nodes, the augmenting path and the new matching. Explain why the final matching you obtain is optimal.

(e) Find a minimum node-cover for the given graph. How does the size of the node-cover correspond to the matching you found in the previous question? Why?

(f) Find an edge-colouring of cardinality four in the graph by repeatedly finding and removing matchings involving all vertices of maximum degree. All steps must be explicitly shown.


Question 2 Suppose teachers x1, x2, x3, x4 have to teach classes y1, y2, y3, y4, y5, y6 according to the following teacher/class allocation table:

(a) What is the minimum possible number of periods used in this allocation. State the theorem(s) that allow you to know this without doing a decomposition?

(b) Calculate the minimum number of periods using a single 1’s decomposition. At each step, indicate which rows/columns have the maximum sum.

(c) Construct a timetable using the minimum number of periods.


Question 3 Consider the following formulation of the weighted assignment problem, where xij is 1 if and only if task i is assigned to worker j.

(a) Consider now that each worker can execute a maximum of not one, but two tasks. How would you modify the original problem? (Note that in this version of the problem, some workers might be assigned to no task).

(b) Consider again the original problem and assume that each task i takes a time tij to be executed by worker j. Assume also that each worker j has bj units of time available and can execute any number of tasks as long as they can finish in his available time bj. Modify the problem to represent this situation. (Note that in this version of the problem, some workers might be assigned to no task).

(c) Consider the original problem and the following data for cij, where the workers are shown in the rows and tasks in the columns. Solve the problem using the algorithm seen in class. Present at least 2 different optimal assignments.





End of Exam