Math 2056W19 Assignment: Graph Theory, Tree Algorithms, and Traversals

This document presents solutions to a Math 2056 assignment focused on graph theory and tree structures. The assignment includes true/false questions testing fundamental concepts of graph theory, such as circuits, chromatic numbers, and tree properties. It also requires students to perform breadth-first and depth-first searches on a given graph to produce spanning trees. Furthermore, the assignment delves into the analysis of rooted trees, asking questions about root, internal vertices, leaves, children, siblings, descendants, ancestors, parent, height, and balance. Additionally, students are tasked with finding pre-order and post-order traversals. The assignment also includes building a binary search tree, writing down the in-order traversal and evaluating prefix and postfix expressions. Finally, the solution demonstrates the application of Prim's and Kruskal's algorithms to find a minimal spanning tree for a weighted graph.

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