Discrete Computational Structures Homework 5

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.

    a. 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)


1

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




2

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

    • 7

    • 4

    • 4

5

h

i

j


2

6








Figure 5: Graph G in Q5.

a. Find the shortest path from a to j using Dijkstra's algorithm. Clearly show each step.
(10 pts)

    b. Find a minimum spanning tree with root as vertex "a" using Prim’s algorithm in Section 11.5 of the textbook.

Explicitly show every step of computation and draw the resulting spanning tree.    (10 pts)


























3

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)

    g. 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)

    i. 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)

    j. 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)

    k. 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)

    l. What is the maximum height to create a binary search tree containing k vertices. Justify your answer.(1 pts)














4

    • Regulations

        1. 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.

        2. 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.

        3. Late Submission: Not allowed

        4. Cheating: We have zero tolerance policy for cheating. People involved in cheating will be punished according to the university regulations.

        5. Newsgroup: You must follow the odtuclass discussions (https://odtuclass.metu.edu.tr) for discussions and possible updates on a daily basis.

        6. 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