Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: zz-x2580
COMP9020 Assignment
Submission is through inspera. Your assignment will be automatically submitted at the above due date. If
you manually submit before this time, you can reopen your submission and continue until the deadline.
If you need to make a submission after the deadline,. Unless you are granted Special Consid-
eration, a lateness penalty of 5% of raw mark per 24 hours or part thereof for a maximum of 5 days will
apply. You can request an extension up to 5 days after the deadline.
Answers are expected to be provided either:
• In the text box provided using plain text, including unicode characters and/or the built-in formula
editor (diagrams can be drawn using the built-in drawing tool); or
• as a pdf (e.g. using LATEX) – each question should be submitted on its own pdf, with at most one pdf
per question.
Handwritten solutions will be accepted if unavoidable, but we don’t recommend this approach as the
assessments are designed to familiarise you with typesetting mathematics in preparation for the final
exam and for future courses.
Discussion of assignment material with others is permitted, but the work submitted must be your own in
line with the University’s plagiarism policy.
Problem 1 (22 marks)
Eight houses are lined up on a street, with four on each side of the road as shown:
Each house wants to set up its own wi-fi network, but the wireless networks of neighbouring houses
– that is, houses that are either next to each other (ignoring trees) or over the road from one another
(directly opposite) – can interfere, and must therefore be on different channels. Houses that are suffi-
ciently far away may use the same wi-fi channel. Your goal is to find the minimum number of different
channels the neighbourhood requires.
• Model this as a graph problem. Remember to:
a) Clearly define the vertices and edges of your graph. 6 marks
b) State the associated graph problem that you need to solve. 4 marks
c) Give the solution to the graph problem corresponding to this scenario; and determine the mini-
mum number of wi-fi channels required for the neighbourhood? 4 marks
d) How do your answers to (a)–(c) change if a house’s wireless network can also interfere with those
of the houses to the left and right of the house over the road? 8 marks
Problem 2 (36 marks)
For the purpose of this question, consider a “vertex rearranging function” for a graph G = (V, E) is
a function φ : V → V that rearranges the vertices of G while preserving the graph’s structure. This
1
means that if there is an edge between vertices u and v in G, then there must also be an edge between
φ(u) and φ(v) in G, and if there is no edge between u and v, then there is none between φ(u) and
φ(v). In other words, φ is a bijective map from V to V such that
(u, v) ∈ E
implies (φ(u), φ(v)) ∈ E and (u, v) /∈ E implies (φ(u), φ(v)) /∈ E.
a) Consider the following graph G = ({1, 2, 3, 4}, {{1, 2}, {2, 3}, {1, 3}, {3, 4}}):
Show that this graph only has one possible non-trivial (that doesn’t simply map each vertex to
itself) “vertex rearranging function” as defined above. 4 marks
b) How many 3-colourings does the graph from part (a) have? (Hint: there are at least 8).
Justify your answer (though partial marks are available for correct answers without justification) 4 marks
c) Here are 8 possible 3-colourings of the graph in part (a):
Find another possible 3-colouring. 2 marks
Now consider an arbitrary graph G = (V, E) where V is the set of vertices and E is the set of edges.
Let C be a set of colours.
Let ColG be the set of all colourings of vertices of G by colours from C. That is,
ColG = {α : V → C such that α is a valid colouring of G}
Define relations R1,R2 ⊆ ColG ×ColG as follows:
2
• (α, β) ∈ R1 if and only if there exists a bijection f : C → C such that for all v ∈ V, f (α(v)) = β(v).
• (α, β) ∈ R2 if and only if there exists a vertex rearrangement function (see (a)) φ : V → V such
that α(v) = β(φ(v)). That is, one colouring can be transformed into the other by rearranging the
vertices according to φ while keeping the colours assigned to each vertex the same.
d) Prove that R1 is an equivalence relation. 6 amrks
e) Prove that R2 is an equivalence relation. 6 marks
f) With the 8 colourings (A-H) of part (c), draw the directed graph with:
• vertices are these 8 colourings (do not include the extra one found in part (c))
• edges given by the relation R1
4 marks
g) With the 8 colourings (A-H) of part (c), draw the directed graph with:
• vertices are these 8 colourings (do not include the extra one found in part (c))
• edges given by the relation R2
4 marks
h) How do R1 and R2 partition the set of colourings {A, . . . H} respectively? 4 marks
Consider the directed graph obtained by associating each vertex to a colouring and adding an edge
between two vertices α and β if (α, β) ∈ R1 ∪ R2.
We define two colourings α and β as being distinct when there does not exist a path between α and β
on this graph.
i) How many colourings in A-H are distinct? 2 marks
Problem 3 (12 marks)
Let S be a set.
a) Show that for any set T and any function f : S→ T, the relation R f ⊆ S× S, defined as:
(s, s′) ∈ R f if and only if f (s) = f (s′)
is an equivalence relation. 6 marks
b) Show that if R ⊆ S × S is an equivalence relation, then there exists a set T and a function
fR : S→ T such that:
(s, s′) ∈ R if and only if fR(s) = fR(s′)
6 marks
Problem 4 (5 marks)
Show that for any sets A, B,C there is a bijection between A(B×C) and (AB)C. 5 marks
3
Advice on how to do the assignment
Collaboration is encouraged, but all submitted work must be done individually without consulting
someone else’s solutions in accordance with the University’s “Academic Dishonesty and Plagiarism”
policies.
• Assignments are to be submitted in inspera.
• When giving answers to questions, we always would like you to prove/explain/motivate your
answers. You are being assessed on your understanding and ability.
• Be careful with giving multiple or alternative answers. If you give multiple answers, then we
will give you marks only for your worst answer, as this indicates how well you understood the
question.
• Some of the questions are very easy (with the help of external resources). You may make use
of external material provided it is properly referenced1 – however, answers that depend too
heavily on external resources may not receive full marks if you have not adequately demonstrated
ability/understanding.
• Questions have been given an indicative difficulty level:
Pass Credit Distinction High distinction
This should be taken as a guide only. Partial marks are available in all questions, and achievable
by students of all abilities.
1Proper referencing means sufficient information for a marker to access the material. Results from the lectures or textbook
can be used without proof, but should still be referenced.
