Chapter 11: Q20E (page 756)
How many leaves does a full \(3\)-ary tree with \({\bf{100}}\) vertices have?
There are \({\bf{100}}\) leaves.
Over 22 million students worldwide already upgrade their learning with Vaia!
All the tools & learning materials you need for study success - in one app.
Get started for free
Find a maximum spanning tree for the weighted graph in Exercise \(4\).
a) What is a prefix code?
b) How can a prefix code be represented by a binary tree?
Show that a subgraph \({\bf{T = }}\left( {{\bf{V,F}}} \right)\) of the graph \({\bf{G = }}\left( {{\bf{V,E}}} \right)\) is an arborescence of G rooted at r if and only if T contains r, T has no simple circuits, and for every vertex \({\bf{v}} \in {\bf{V}}\) other than r, \({\bf{de}}{{\bf{g}}^ - }\left( {\bf{v}} \right){\bf{ = 1}}\) in T.
Is the rooted tree in Exercise \(3\) a full \({\bf{m}}\)-ary tree for some positive integer \({\bf{m}}\)?
a. What is a minimum spanning tree of a connected weighted graph\(?\)
b. Describe at least two different applications that require that a minimum spanning tree of a connected weighted graph be found.
What do you think about this solution?
We value your feedback to improve our textbook solutions.
