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

MAST20018 – Discrete Mathematics and Operations Research

Assignment 2

1.  Consider the graph below:

e

 f

g

(a)  Starting with the matching M = {{c．d}}, iteratively extend M until a maximum matching is found.   Do this by finding augmenting paths at each iteration.   Avoid using trivial augmenting paths (that do not contain edges in the current matching) whenever possible. Show all working.

(b) Find the edge-chromatic number of the graph by finding a minimum edge-colouring. Pro- vide an argument for how you know your solution is optimal.

(c) Find a minimum vertex covering of the graph.

(d)  Compare your solutions to (a) and (c) and provide discussion and reasoning for the result. (e) Is the graph an interval graph? Provide reasons for your answer.

2. Prove that every interval graph is chordal.

3.  Consider the problem of Fair Division.

(a) Describe in your own words why the problem of Fair Division is a complex problem, and explain what we mean by “fair” .

(b) Prove formally that the Adjusted Winner Method of fair division is envy free.