CENG223 -the5 - Solved

Discrete Computational Structures
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.