COMP9020 Assignment 2 2024 Term 1 Due: Thursday, 14th March, 18:00 (AEDT)
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, please use this link to request an extension:
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.
b) State the associated graph problem that you need to solve.
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
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
6 marks
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) ConsiderthefollowinggraphG=({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.
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)
c) Here are 8 possible 3-colourings of the graph in part (a):
Find another possible 3-colouring.
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→CsuchthatαisavalidcolouringofG} Define relations R1, R2 ⊆ ColG × ColG as follows:
4 marks
4 marks
2 marks
• (α,β)∈R1 ifandonlyifthereexistsabijection f :C→Csuchthatforallv∈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.
e) Prove that R2 is an equivalence relation.
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
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
h) How do R1 and R2 partition the set of colourings {A, . . . H} respectively?
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?
Problem 3 (12 marks) Let S be a set.
a) Show that for any set T and any function f : S → T, the relation Rf ⊆ S×S, defined as: (s,s′) ∈ Rf if and only if f(s) = f(s′)
is an equivalence relation.
b) Show that if R ⊆ S × S is an equivalence relation, then there exists a set T and a function
6 marks
4 marks
4 marks
4 marks
2 marks
fR :S→Tsuchthat:
(s, s′) ∈ R if and only if fR(s) = fR(s′)
6 marks
6 marks
5 marks
Problem 4
Show that for any sets A, B, C there is a bijection between A(B×C) and (AB)C.
(5 marks)
6 amrks
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:
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.
Pass
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.
