CSE211 - Homework 3 - Solved

 Discrete Mathematics


Problem 1: Hamilton Circuits                                                                                                               (10+10+10=30 points)
Determine whether there is a Hamilton circuit for each given graph (See Figure 1a, Figure 1b, Figure 1c ). 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 1: The graphs to find Hamilton circuits for Problem 1

(a)      (Solution)

(b)     (Solution)

(c)      (Solution)

1

– Homework #3                                                                                                                                                                                        2

Problem 2: Graph Isomorphism                                                                                                          (10+10+10=30 points)
Determine whether each pair of graphs (see Figure 2, Figure 3, Figure 4) is isomorphic or not.

Note: If you answer only ”isomorphic” or ”not isomorphic”, you cannot get points. Show your work.

 

Figure 2: The graphs Ga1(left) and Ga2(right) to find isomorphism for Problem 2(a)

 

Figure 3: The graphs Gb1(left) and Gb2(right) to find isomorphism for Problem 2(b)

 

Figure 4: The graphs Gc1(left) and Gc2(right) to find isomorphism for Problem 2(c)

(a)    (Solution)

(b)   (Solution)

(c)    (Solution)

– Homework #3                                                                                                                                                                                        3

Problem 3: Euler Circuits
(10+10=20 points)

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

 

                                       (a) The graph G3a                                                                                                                     (b) The graph G3b

Figure 5: The graphs to find Euler circuits for Problem 3

(Solution)

Problem 4: Applications on Graphs                                                                                                                          (20 points)
Schedule the final exams for Math 101, Math 243, CSE 333, CSE 346, CSE 101, CSE 102, CSE 273, and CSE 211, using the fewest number of different 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.

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

Hint 2: Check the website

(Solution)