Jaypee Institute of Information Technology (JIIT) 2007 B.Tech MATH --DISCRETE MATH-GRAPH - Question Paper

Tutorial Sheet – VI (Graphs part 2)

1. For every of the provided graph, determine the sum of the in-degrees and the sum of the out-degrees of the vertices directly. Show that they are both equal to the number of edges in the graph.













2. Construct the underlying undirected graph for the above directed graphs.
3. Question No. 9.5, 9.23, 9.24 (Schaum’s Series)
4. Let V = {2,3,4,9,15} and E = { (x, y): x < y and x is relatively prime to y }
(Note that E is a relation on V)
(a) Draw the directed graph G(V, E).
(b) Is G strongly connected? Is G weakly connected? Is G unilaterally connected?
5. Answer these ques. about the rooted tree illustrated.
Which vertex is the root?
(a) Which vertices are internal?
(b) Which vertices are leaves?
(c) Which vertices are children of j?
(d) Which vertex is the parent of h?
(e) Which are siblings of o?
(f) Which vertices are ancestors of m?
(g) Which vertices are descendants of b?





6. Is the rooted tree in Q. No. five a full m-ary tree for a few positive integer m?

7. The subsequent addresses are in random order:
2.1.1, 3.1, 2.1, 1, 2.2,.1.2, 0, 3.2, 2.2, 1.1, 2, 3.1.1, 2.2.1, 3, 2.2.1.1
(a) Place the addresses in lexicographical order.
(b) Draw the corresponding rooted tree?
(c) Identify the path p from the root 0 to every of the subsequent vertices, and obtain the level number of the vertex: (i) 2.2.1.1 (ii) 3.1 (iii) 2.1.1
(d) obtain the leaves of T.
8. ques. No. 9.10 (Schaum’s Series)

9. ques. No. 9.33 (Schaum’s Series)
10. What is the value of the prefix expression Ans: 3.
11. Represent the expression (x + xy) + (x/y) and x + ((xy + x)/ y) using an ordered
rooted tree.
12. Represent using an ordered rooted tree.
13. Write the expressions of Q. No. 11 and Q. No. 12 in prefix form.
14. ques. No. 9.34, 9.35 (Schaum’s Series)
15. Consider the digraph G of ques. No. 9.34, determine how many paths of length three exist in g and which vertices are connected by a path of length 3.
16. Draw the subtree of the tree (in Q. No. 5) that is rooted at
(a) a (b) c (c) e.
17. provide an example of a complete bipartite graph , m and n are positive integers,
which is a tree.
18. Example 10.1 (Schaum’s Series)
19. Consider the subsequent trees












Tree one Tree two Tree 3

(a) Determine the order in which a preorder traversal visits the vertices of the above
rooted trees.
(b) Determine the order in which an inorder traversal visits the vertices of the above
rooted trees.
(c) Determine the order in which a postorder traversal visits the vertices of the above
rooted trees.

Earning:   Approval pending.