Math 2056W19 Reading Assignment

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