Chapter 11: Q42E (page 757)
Show that a center should be chosen as the root to producea rooted tree of minimal height from an unrooted tree.
A tree is a connected graph having no simple circuits.
A rooted tree is a tree in which one vertex has been designated as the root and every edge is directed away from the root.
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
Show that a simple graph is a tree if and only if it contains no simple circuits and the addition of an edge connecting two nonadjacent vertices produces a new graph that has exactly one simple circuit (where circuits that contain the same edges are not considered different).
What is the level of each vertex of the rooted tree in Exercise \(4\)?
Find a maximum spanning tree for the weighted graph in Exercise \(4\).
Show that postorder traversals of these two ordered rooted trees produce the same list of vertices. Note that this does not contradict the statement in Exercise 27, because the numbers of children of internal vertices in the two ordered rooted trees differ.
Well-formed formulae in prefix notation over a set of symbols and a set of binary operators are defined recursively by these rules:
Sollin's algorithm produces a minimum spanning tree from a connected weighted simple graph \({\bf{G = (V,E)}}\) by successively adding groups of edges. Suppose that the vertices in \({\bf{V}}\) are ordered. This produces an ordering of the edges where \({\bf{\{ }}{{\bf{u}}_{\bf{0}}}{\bf{,}}{{\bf{v}}_{\bf{0}}}{\bf{\} }}\) precedes \({\bf{\{ }}{{\bf{u}}_{\bf{1}}}{\bf{,}}{{\bf{v}}_{\bf{1}}}{\bf{\} }}\) if \({{\bf{u}}_{\bf{0}}}\) precedes \({{\bf{u}}_{\bf{1}}}\) or if \({{\bf{u}}_{\bf{0}}}{\bf{ = }}{{\bf{u}}_{\bf{1}}}\) and \({{\bf{v}}_{\bf{0}}}\) precedes \({{\bf{v}}_{\bf{1}}}\). The algorithm begins by simultaneously choosing the edge of least weight incident to each vertex. The first edge in the ordering is taken in the case of ties. This produces a graph with no simple circuits, that is, a forest of trees (Exercise \({\bf{24}}\) asks for a proof of this fact). Next, simultaneously choose for each tree in the forest the shortest edge between a vertex in this tree and a vertex in a different tree. Again the first edge in the ordering is chosen in the case of ties. (This produces a graph with no simple circuits containing fewer trees than were present before this step; see Exercise \({\bf{24}}\).) Continue the process of simultaneously adding edges connecting trees until \({\bf{n - 1}}\) edges have been chosen. At this stage a minimum spanning tree has been constructed.
Show that the addition of edges at each stage of Sollin’s algorithm produces a forest.
What do you think about this solution?
We value your feedback to improve our textbook solutions.
