Description
Question 1 (15 pts)
Let S be a set containing the subsets of the set f0; 1; 2g and R be a relation on S S, de ned as
S = fw : w is a set; w 2 P (f0; 1; 2g)g
R = f(w1; w2) : w1 2 S ; w2 2 S and w1 is a subset of w2g
where P (f0; 1; 2g) denotes the powerset of the set f0; 1; 2g.
-
Draw R as a directed graph. (For this part (only for a) you can draw by your hand or any tool you want and
then include it as an image.) |
(2 pts) |
b. Prove that (S; R) is a poset. |
(4 pts) |
c. Is (S; R) a total order? Prove your answer. |
(3 pts) |
d. Draw a Hasse diagram for (S; R). State the maximal and minimal elements. |
(4 pts) |
e. Identify whether (S; R) constitutes a lattice or not. Explain your answer. |
(2 pts) |
Question 2 (24 pts)
Given the directed graph G in Figure 1, answer the questions.
a d
g |
||||||||||
c |
e |
|||||||||
b |
f |
|||||||||
Figure 1: Graph G in Q2. |
||||||||||
a. Provide an adjacency list representation of G. |
(3 pts) |
|||||||||
b. Provide an adjaceny matrix representation of G. |
(3 pts) |
|||||||||
c. Compute indegrees and outdegrees of every vertex in V . |
(3 pts) |
d. |
List 6 di erent simple paths of length 4 in G. |
(3 pts) |
e. |
List all simple circuits of length 3 in G. |
(3 pts) |
f. |
Prove that G is weakly-connected. |
(3 pts) |
g. |
Identify strongly-connected components of G. |
(3 pts) |
h. How many di erent paths of length 3 exist from d to g in the subgraph H of G induced by the vertices
fd; e; f; gg V ? (3 pts)
Question 3 (16 pts)
Given the undirected graph G in Figure 2, answer the following questions using clear formalism.
c f
b d e g
a |
h |
Figure 2: Graph G in Q3. |
|
a. Prove whether G has a Euler path or not. |
(4 pts) |
b. Prove whether G has a Euler circuit or not. |
(4 pts) |
c. Prove whether G has a Hamiltonian path or not. |
(4 pts) |
d. Prove whether G has a Hamiltonian circuit or not. |
(4 pts) |
Question 4 |
(10 pts) |
Determine if the following two graphs (G (Figure-3) and G’ (Figure-4)) are isomorphic or not. Justify your answer.
a
d c
b e
Figure 3: Graph G
a’
e’ b’
d’ c’
Figure 4: Graph G’
Question 5 (20 pts)
Given the undirected graph G in Figure 5, answer the questions.
-
-
-
-
-
b
2
c
3
d
3
5
7
2
6
7
2
a
5
e
4
f
4
g
6
k
-
-
-
-
Question 6 (15 pts)
Answer options a-g using the binary tree T in Figure 6. Vertices of T are marked with <identifier:key> an-notations. Note that T has the vertex “a” as its root. Use the notational conventions in your textbook to decide whether a vertex is left or right child of some vertex whenever applicable.
a:17
b:13 c:24
d:19 e:43
f:23 |
g:58 |
|
Figure 6: Tree T in Q6 options a, b, c, d, e, f, g. |
||
a. What are the number of vertices, the number of edges and the height of T ? |
(1 pt) |
|
b. Carry out a preorder traversal of T and write down the order in which vertices are visited. |
(1 pt) |
|
c. Carry out a postorder traversal of T and write down the order in which vertices are visited. |
(1 pt) |
|
d. Carry out an inorder traversal of T and write down the order in which vertices are visited. |
(1 pt) |
|
e. Is T a full binary tree? Justify your answer. |
(1 pt) |
|
f. Is T a complete binary tree? Justify your answer. |
(1 pt) |
-
Is T a binary search tree using provided keys under comparison with respect to the relation de ned on
Z Z? Justify your answer. (1 pt)
h. What is the minimum number of nodes for a full binary tree with height 5 ? (2 pt)
-
Construct a complete binary search tree by using the following set of integer keys f1; 2; 3; 4; 5; 6g employing
the relation de ned on Z Z. (2 pts)
-
Using the binary search tree in i, give sequences of vertices that are probed in order to nd vertices with key
values 1 and 6, repsectively. (1 pt)
-
Construct a spanning tree for the directed graph G in Figure 1 via breadth- rst search under the assumption
that unvisited vertices are selected for expansion in reverse alphabetic order of vertex identi ers. (2 pts)
-
What is the maximum height to create a binary search tree containing k vertices. Justify your answer.(1 pts)
-
Regulations
-
-
You have to write your answers to the provided sections of the template answer le given. Other than that, you cannot change the provided template answer le. If a latex structure you want to use cannot be compiled with the included packages in the template le, that means you should not use it.
-
-
-
Do not write any other stu , e.g. question de nitions, to answers’ sections. Only write your answers. Otherwise, you will get 0 from that question.
-
-
-
Late Submission: Not allowed
-
-
-
Cheating: We have zero tolerance policy for cheating. People involved in cheating will be punished according to the university regulations.
-
-
-
Newsgroup: You must follow the odtuclass discussions (https://odtuclass.metu.edu.tr) for discussions and possible updates on a daily basis.
-
-
-
Evaluation: Your latex le will be converted to pdf and evaluated by course assistants. The .tex le will be checked for plagiarism automatically using “black-box” technique and manually by assistants, so make sure to obey the speci cations.
-
-
Submission
Submission will be done via odtuclass. Download the given template le, “hw5.tex”, when you nish your exam upload the .tex le with the same name to odtuclass.
Note: You cannot submit any other les. Don’t forget to make sure your .tex le is successfully compiled in Inek machines using the command below.
$ pdflatex hw5.tex
5