Description

CENG223
Discrete Computational Structures
Take Home Exam 5

Question 1
Given A = {1,2,3}, we construct a partial order set (POSET) as (P(A),⊆).
a) Draw the Hasse diagram.
b) Is it a lattice?
c) Find the maximal elements.
d) Find the minimal elements.
e) Is there a greatest element?
f) Is there a least element?
g) Find Least Upper Bounds (LUBs) of {1} and {3}.
Question 2

Consider the graph G in Figure 1 to answer the following questions. Explain all the answers.
a) What is the sum of degrees of all nodes of G?
b) What is the number of non-zero entries in the adjacency matrix representation of G?
c) What is the number of non-zero entries in the incidence matrix representation of G?
d) Does G have a complete graph with at least three vertices as a subgraph? If yes, draw this subgraph.
e) Is G a bipartite graph? If yes, explain briefly; if no, remove the edges such that the resulting subgraph of G will be a bipartite graph.
f) How many directed graphs are there that have G as their underlying undirected graph?
g) What is the length of the simple longest path in G? Explain your answer.
h) What is the number of connected components of G? Explain your answer.
i) Is there an Euler circuit in G? If yes, give such a circuit; if no, state the reason.
j) Is there an Euler path in G? If yes, give such a path; if no, state the reason.
k) Does G have a Hamilton circuit? If yes, find such a circuit; if no, justify your answer.
l) Does G have a Hamilton path? If yes, find such a path; if no, justify your answer.
Question 3

(a) G (b) H
Figure 2: Graph G and H in Q3.
Determine whether G and H are isomorphic, or not. Explain your answer.
Question 4
Find the shortest path from vertex a to vertex j in the following weighted graph G (see Figure 3) using Dijkstra’s algorithm. Describe the steps clearly.

Question 5
Use either Kruskal’s or Prim’s algorithm to find a minimum spanning tree for the graph G given below (Figure 4). Please state the algorithm you choose at the beginning of your solution.

a) Write the order in which the edges are added to the tree.
b) Draw the minimum spanning tree.
c) Is the minimum spanning tree unique? Justify your answer.
Question 6
Answer the following questions using the binary tree T in Figure 5. Note that T has the vertex p 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) What are the number of vertices, the number of edges and the height of T?
b) Carry out a postorder traversal of T and write down the order in which vertices are visited.
c) Carry out an inorder traversal of T and write down the order in which vertices are visited.
d) Carry out a preorder traversal of T and write down the order in which vertices are visited.
e) Is T a full binary tree? Justify your answer.
1 Regulations
1. You have to write your answers to the provided sections of the template answer file given.
2. Do not write any extra stuff like question definitions to the answer file. Just give your solution to the question. Otherwise you will get 0 from that question.
3. Late Submission: Not allowed!
5. Newsgroup: You must follow the newsgroup (odtuclass.metu.edu.tr) for discussions and possible updates on a daily basis.
2 Submission
Submission will be done via odtuclass. Download the given template answer file ”the5.tex”. When you finish your exam upload the .tex file with the same name to odtuclass.
Note: You cannot submit any other files. Don’t forget to make sure your .tex file is successfully compiled in Inek machines using the command below.
$ pdflatex the5.tex