COMP9020 Assignment 2 – Guide 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.
Objectives and Outcomes
The purpose of this assignment is to build your mathematical maturity in the areas of Graph Theory, Relations, and Functions. Most questions are presented at an abstract level so that the consequences are very general, and can be applied in a variety of situations: not just later on in the course, but also beyond. The specific motivation for each problem can be summarised as follows:
Problem 1: The aim of this question is to model a concrete (“real-world”) problem abstractly using Graph Theory. An abstract model lets us: identify the important aspects of a problem and ignore the extraneous; identify connections with other, seemingly unrelated problems; and make use of other, more general, tools and results to solve the specific problem. We will revisit this problem in Assignment 4, where we will model it with Propositional Logic.
Problem 2: This question brings together the topics of Graph Theory, Relations and Functions. It ex- plores the symmetries of graph colourings (i.e. ways in which different colourings can be seen as essentially the same). We will revisit symmetries when we cover counting techniques in Week 9.
Problem 3: This question shows another, very useful, characterization of equivalence relations, connect- ing them with functions. This goes along with the characterization in terms of partitions (i.e. a connection with sets) described in lectures. Most of the examples of equivalence relations given in lectures and quizzes (e.g. Quiz 4, 2.1) fit this characterization.
Problem 4: The use of exponential notation for describing sets of functions extends beyond compar- ing cardinalities. This question demonstrates the set-theoretical analogue of the rule abc = (ab)c. This has applications in computer science as it demonstrates how functions of two inputs can be constructed from functions of just a single input. This process is known as Currying.
After completing this assignment, you will:
• Beabletomakerigorousargumentsaboutthefoundationalstructuresusedindiscretemathematics [All problems]
• Be able to create and reason about abstract models of concrete (“real-world”) problems and objects [Problem 1]
• Understand several deeper connections between different topics of the course [Problem 2]
Advice on how to do assignments
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.
• In the assignment specification, 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.
Specific advice on how to do this assignment Problem 1
• For part (a) you should describe how to construct the graph in such a way that it is clear how to construct a graph for variations of the problem. Then show what the graph looks like for this particular problem.
• A “graph problem”, for (b), is a question about graphs. Examples of the types of “graph prob- lems” that may be suitable include:
– Is the resulting graph planar?
– Does the graph have an Eulerian/Hamilton circuit? – What is the chromatic/clique number of the graph? – Is the graph connected?
– Is the graph acyclic?
– What is the maximum degree of any vertex?
A distinction-level answer would also provide a one to two sentence justification of why the associated graph problem is correct.
• For part (c), you should answer, with justification, the graph problem on your given graph and then translate that solution to a solution to “what is the minimum number of wifi channels needed?” Remember to show all aspects of the solution to the graph problem: for example if the problem is to find the chromatic number of the graph, you need to show that it can be coloured with k colours, and it cannot be coloured with fewer than k colours.
• As an example, here is an (HD-level) solution for the exam-timetabling problem given in lectures (Puzzle 5 in “Lecture 8”):
(a) We can model the exam timetabling problem with the following graph:
– Vertices: A vertex for every subject
– Edges: An edge between two vertices if the corresponding subjects have at least one student in common
For this particular problem, this would result in the following graph: Potions
Charms Herbology
Transfiguration Astronomy
(b) If we model each exam timeslot with a colour, then assigning subjects to exam slots is modelled by colouring vertices. The requirement that no student has two or more exams at the same time then corresponds to no edge having both its endpoints being the same colour (i.e. the vertex colouring is a valid colouring). So the problem of finding the minimum number of exam timeslots with no conflicts corresponds to the graph problem of finding the chromatic number of the resulting graph.
(c) The graph that models our problem is C5 – the 5 vertex cycle. From lectures we know that the chromatic number of this graph is 3. For example, here is a 3-colouring of the graph:
Potions
Charms Herbology
Transfiguration Astronomy
and we cannot colour the vertices with fewer colours because C5 is not bipartite. This corre- sponds the following allocation of subjects to three timeslots (which is the fewest possible):
Timeslot 1 Potions Transfiguration
Timeslot 2 Timeslot 3 Charms Astronomy
Herbology
(d) If Defence Against the Dark Arts (DADA) was added with Harry, Hermione and Ron, then the resulting graph would look like:
Potions
Charms Herbology
DADA
Transfiguration Astronomy
We can colour this graph with three colours (as shown) and cannot do better because it contains K3 as a subgraph. So the chromatic number of this graph is also 3. Therefore we can still allocate the subjects to three timeslots (which is the fewest possible):
Timeslot 1 Potions Astronomy
Timeslot 2 Charms Herbology
Timeslot 3 Transfiguration DADA
Problem 2
• In part (a), you need to understand what is required of a “vertex rearranging function”. A vertex rearranging function is essentially an isomorphism (as seen in the lecture) of a graph onto itself. This is also called an automorphism. Remember from the lecture that an isomorphism needs to be bijective, every vertex is mapped onto another vertex one to one.
To answer the question, you need to understand that the function keeps the graph structurally the same. To prove that there is only one way to map the vertices to themselves non-trivially (a trivial mapping would be mapping each vertex to itself) you must look for the unique elements of the graph (like vertices of specific degree).
A good place to start would be to list the degrees of each vertex. Once you’ve done that you can determine which vertex can be rearranged without altering the degree.
The question asks you to prove that the mapping you find is the only non-trivial one, so make sure to argue why other mappings would not be possible. Once you’ve find a mapping, make sure to check that it does indeed satisfy the conditions of a vertex rearranging function.
• In part (b) you’re asked to figure out how many 3-colourings the graph has. Make sure to argue how you came to that conclusion, don’t just list the colourings but actually reason about how you would count them.
For example, if I am given the following graph:
and asked to count the number of 2-colourings. I reason as follows: 1 can be one of two colours. Once a colour for 1 has been set, for the property of colourings to be preserved, there is only one possible colour for 2. Once a colour for 2 is set, there is only one possible colour for 3. Therefore we have 2 × 1 × 1 = 2 colourings.
• In parts (d) and (e), you will have to show that that “rearrangement functions” (also known as permutations) applied to either the domain (for R2) or the co-domain (for R1) of colourings form equivalence relations on the colourings. To do so make sure that you prove each property of equivalence relations as detailed in the guide to Problem 3.
As an example of how R1 and R2 relate colourings, let ColG be the 3-colourings of the graph of part (a) and consider the subset of these colourings given in part (f).
– Because colouring A can be transformed into colouring B with the function f : C → C given by:
f (blue) = blue f (red) = orange f (orange) = red we have that (A, B) ∈ R1.
– Because colouring A can be transformed into colouring E with the function f : V → V given by:
f(1)=2 f(2)=1 f(3)=3 f(4)=4 we have that (A, E) ∈ R2
• For parts (d) and (e), note that you are not asked to prove something about a specific graph, but rather the colourings of an arbitrary graph. Make sure that your proof is general and applies to any graph.
• For parts (f)-(h), you are asked to model relations on some of the colourings of the example graph from a-c as a (new) graph. In this new graph the vertices represent a possible colouring and a directed edge represents that the two colourings in the edge are in the relation (in the same order as in the edge). Get an understanding of how R1 and R2 relate two colourings to build the graph. You can use the fact that R1 and R2 are equivalence relations (which you have already proved for general graphs) to avoid having to do every pairwise comparison (look for transitive edges, use symmetry).
• Part (i) asks you to combine the relations you have modelled in the previous questions into one directed graph R1 ∪ R2. You must then isolate the strongly connected components of the graph into equivalence classes of distinct colourings. The idea behind the question is to see in a concrete example how eliminating the way we label the vertices or the colours impacts the number of distinct colourings. In other words, how many colourings of the graph were only superficially distinct, rather than fundamentally so.
Extension question (not worth any marks)
How many distinct 3-colourings of the graph are there when we consider all 3-colourings and not just the colourings A-H?
Problem 3
• To prove something is an equivalence relation, you need to identify the key properties of an equivalence relation, and then show that your relation satisfies those properties. As an example, here is a sample proof (HD-level) that R = {(m, n) ∈ N × N : m2 =(5) n2 } is an equivalence relation:
To show R is an equivalence relation, we must show that it is reflexive (R), symmetric (S), and transitive (T).
– (R): We have, for all n ∈ N, 5|n2 − n2. Therefore n2 =(5) n2. Therefore (n, n) ∈ R, and so R is reflexive.
– (S): Suppose (m,n) ∈ R. Then m2 =(5) n2, so 5|m2 −n2. But then 5|n2 −m2, so n2 =(5) m2, and therefore (n, m) ∈ R. Therefore R is symmetric.
– (T): Suppose (m, n) ∈ R and (n, p) ∈ R. Then m2 =(5) n2 and n2 =(5) p2. So 5|m2 − n2 and 5|n2 − p2. Therefore 5|(m2 − n2) + (n2 − p2), that is, 5|m2 − p2. Therefore m2 =(5) p2, so (m, p) ∈ R. Therefore R is transitive.
As R is reflexive, symmetric and transitive, we have that R is an equivalence relation.
• For part (a) make sure you show that the result holds for any sets S, T and function f : S → T. That is, you should show the result without relying on any particular attributes of S, T or f. Partial marks are available if you show the result for a specific choice of S, T and/or f .
• For an example of what is being asked in (b), suppose R is the equivalence relation {(m, n) ∈ N×N:m2 =(5) n2}.ThenbytakingTtobetheset{a,b,c}and fR :N→Ttobethefunction
a ifn2=(5)0 f(n)= b ifn2=(5)1 ,
c ifn2=(5)4
f(n)= f(m) ifandonlyif n2 =(5) m2 ifandonlyif (n,m)∈R.
This example only works for this specific equivalence relation R, part (b) is asking you to show the result for any equivalence relation R.
• For part (b) note that you are proving a statement of the form “There exists”. So you can choose the set T and the function fR : S → T, but it should be made clear how to make the choice of T (and fR) based on R – you don’t get to choose R.
• A further hint for (b): Do we know of anything related to s and s′ that is “equal” when s and s′ are equivalent?
Problem 4
• To get full marks for this question, your proof should apply to all sets, not just finite sets (i.e. you cannot appeal to cardinalities). An argument that appeals to set cardinalities will be eligible for partial marks.
• The most difficult part of this question is comprehending the two sets: AB×C and (AB)C. Ques- tion 2.2 on Quiz 4 is designed to help understand these sets with some concrete examples:
we have the following:
– f:Σ∗×Σ∗→Σ∗,givenbyf(v,u)=uv – g:Σ∗ →Σ∗,givenbyg(w)= f(01,w) – h:Σ∗ →Σ∗,givenbyh(w)= f(10,w)
If we take A = B = C = Σ∗ then f is an example of a function in AB×C. It is a function that takes two inputs (one from B and one from C) and gives an output in the set of A.
g and h are functions that are defined from f in an almost identical way. In fact you could define a function F so that g = F(01) and h = F(10). What are the domain and co-domain of F? Well F takes as input a word (element of C) and returns a function (which maps words to words) – i.e. an element of AB. That is F : C → AB, or F is an element of (AB)C.
• Your task for this question is to show that for every function f (for general sets A, B and C) there is a corresponding function like F and vice-versa.
• Be careful with bracketing: in the above example if I wanted to talk about g(w) in terms of F this would be something like [F(01)](w).
