Mathematics Homework #3 Solution

Course Policy: Read all the instructions below carefully before you start working on the assignment, and before you make a submission.

It is not a group homework. Do not share your answers to anyone in any circumstance. Any cheating means at least -100 for both sides.

Do not take any information from Internet. No late homework will be accepted.

For any questions about the homework, send an email to gizemsungu@gtu.edu.tr

The homeworks (both latex and pdf les in a zip le) will be submitted into the course page of Moodle. The latex, pdf and zip les of the homeworks should be saved as "Name Surname StudentId".ftex, pdf,

zipg.

If the answers of the homeworks have only calculations without any formula or any explanation -when needed- will get zero.

Writing the homeworks on Latex is strongly suggested. However, hand-written paper is still accepted IFF hand writing of the student is clear and understandable to read, and the paper is well-organized. Otherwise, the assistant cannot grade the student’s homework.



Problem 1: Representing Graphs


(10 points)

Represent the graph in Figure 1 with an adjacency matrix. Explain your representation clearly.











Figure 1: The graph for Problem 1

(Solution)
















1
{ Homework #3




Problem 2: Hamilton Circuits

2



(10+10+10=30 points)

Determine whether there is a Hamilton circuit for each given graph (See Figure 2a, Figure 2b, Figure 2c ). If the graph has a Hamilton circuit, show the path with its vertices which gives a Hamilton circuit. If it does not, explain why no Hamilton circuit exists.














(a) The graph G1    (b) The graph G2










(c) The graph G3

Figure 2: The graphs to    nd Hamilton circuits for Problem 1


(a)

(Solution)

(b)

(Solution)

(c)

(Solution)
{ Homework #3




Problem 3: Applications on Graphs

3



(20 points)

Schedule the    nal exams for Math 101, Math 243, CSE 333, CSE 346, CSE 101, CSE 102, CSE 273, and

CSE 211, using the fewest number of di erent time slots, if there are no students who are taking:

both Math 101 and CS 211, both Math 243 and CS 211, both CSE 346 and CSE 101, both CSE 346 and CSE 102, both Math 101 and Math 243, both Math 101 and CSE 333, both CSE 333 and CSE 346

but there are students in every other pair of courses together for this semester.

Note: Assume that you have only one classroom.

Hint 1: Solve the problem with respect to your problem session notes.

Hint 2: Check the website

(Solution)
{ Homework #3




Problem 4: Applications for Hasse Diagram of Relations


Remember the Problem 3 in Homework 2.

4



(40 points)

Write an algorithm to draw Hasse diagram of the given relations in "input.txt" which is given for HW2.

Your code should meet the following requirements, standards and accomplish the given tasks.

Read the relations from the text le "input.txt". You can use your code from HW2 if you implemented to read the le. If you didn’t implement it, please check HW2 to learn how to read the relations from the le.


Determine each relation in "input.txt" whether it is re exive, symmetric, anti-symmetric and transitive with your algorithm from HW2.

In order to draw Hasse diagram, each relation must be POSET. Hence, the relation obeys the following rules:

{ Re exivity

{ Anti-symmetric { Transitivity

If the relation is not a POSET, your algorithm is responsible to CONVERT it to POSET.

{ If the relation is not re exive, add new pairs to make the relation re exive.

{ If the relation is symmetric, remove some pairs which make the relation symmetric. For instance, if the relation has (a, b) and (b, a), remove one of them randomly.

{ If the relation is not transitive, add new pairs which would make the relation transitive.

After the relation becomes POSET, your algorithm should obtain Hasse diagram of the relation and write the diagram with the following format.

{ An example of the output format is given in "exampleoutput.txt". The le has the result of the rst relation in "input.txt".

{ In "output.txt", each new Hasse diagram starts with "n".

{ The relation is (a, a), (a, b), (a, e), (b, b), (b, e), (c, c), (c, d), (d, d), (e, e)

{ The relation is already a POSET so we don’t need to add or remove any pairs.

{ After "n", write the POSET in the next line as it is shown in "exampleoutput.txt".

{ Since the relation is POSET, it becomes (a, b), (b, e), (c, d) after removing re exive and transitive pairs.

{ The following lines give each pair of Hasse diagram.

You can implement your algorithm in Python, Java, C or C++.

Important: Put comments almost for each line of your code to describe what the line is going to do. You should put your source code le ( le name is problem1.f:c; :java; :py; :cppg) and output.txt into your

homework zip  le (check Course Policy).