Math 2056W19 Reading Assignment

This assignment includes True or False questions about trees, problems related to spanning trees, graph traversals, binary search trees, and weighted graphs. It also requires finding the order of edges and total length of the minimal spanning tree using Prim's and Kruskal's algorithms.

Assignment
math 2056W19 reading
APRIL 8, 2019

Ques 1. Answer the following questions True or False.
(a) A tree is an undirected graph with no circuits.
Sol.
True
(b) It is not possible for a simple planar graph to have a chromatic number of 5.
Sol.
True
(c) A rooted tree where every internal vertex has more than m children is called a full m-ary tree.
Sol.
False
(d) If a tree has n vertices, then it hasn−1 edges.
Sol.
True
(e) The height of a rooted tree is the length of the longest simple path that starts at the root and ends
at a leaf.
Sol.
True
(f) A balanced rooted tree has all of its leaves at the same level.
Sol.
False
(g) There is only one algorithm for finding a minimal spanning tree of a graph.
Sol.
False
(h) A graph will have a spanning tree if and only if it is connected.
Sol.
True
(i) A simple connected graph has exactly one spanning tree for each choice of the root.
Sol.
False
(j) The following is a prefix code: a=0 , t=0 , e=101 , f =1110
Sol.

False
Ques 2.
Use breadth—first search and a depth—first search to produce, spanning trees for the graph shown
below. Choose i as the root of each spanning tree.
Sol.
This graph can be redrawn as:
i
eh m nd j
g
a b l
c
of k

Breadth-First Search:
i d h m e j n c g f k o a b l
Depth-First Search:
i d h c g a b l m e j f k o n
Ques 3.
Answer the questions about the rooted tree shown below.
(a) Which vertex is the root?
Sol.
Vertex a
p

(b) Which vertices are internal?
Sol.
Vertex a, b, d, e, g, i and o
(c) Which vertices are leaves?
Sol.
Vertex c, f, h, j, k, l, m, p, q, r and s
(d) Which vertices are children of o ?
Sol.
Vertex q, r and s
(e) Which vertices are siblings of f ?
Sol.
Vertex e and g
(f) Which vertices are descendants of i ?
Sol.
Vertex o, p, q, r and s
(g) Which vertices are ancestors of q?
Sol.
Vertex o, i, d and a
(h) Which vertex is the parent of i?
Sol.
Vertex d
(i) What is the height of the tree?
Sol.
4
(j) Is the tree balanced?
Sol.

No
Ques 4.
For the graph shown find the indicated traversals.
p
(a) the Pre-order traversal
Sol.
a , b , e , j, k , f , g , l, m , c , d , h ,i , o , p
(b) the Post-order traversal
Sol.
j , k , e , f ,l , m, g , b , c , h , o , p ,i , d , a
Ques 5.
a) Build a binary search tree for the following list using numerical order, and then write down the
In-order traversal for the rooted tree you have constructed.
53,42,180,62,16,93,41,410,43

53
42 180
6216
93
41
43 410
In order Traversal: 41, 16, 42, 43, 53, 180, 62, 93, 410

b) What is the value of the prefix expression?
−¿ 2/843
Sol.
8
2∗4−3
¿ 13
c) What is the value of the postfix expression?
732∗−4 ↑ 93/+¿
Sol.
4 ↑7−2∗3+ 9
3
7
Ques 6.
Use Prim's and Kruskal's algorithms to find a minimal spanning tree for the weighted graph shown
below. List the order in which the edges are picked and state the total length of this tree.
Sol.
Prims Algorithm:

a g b c h m i j n k f e d l
Kruskal’s Algorithm
c h a g b m i j n k f e l d