Exercises 391
(b) Is the MCST in graph H unique? If not, find all examples. Find an MCST in the
graph if (3, 4) and (2, 5) must be included. Is such an MCST unique? If not, find
all examples.
- A university has eight buildings that need to be connected so that each building's
computer network is accessible to the networks in the other buildings. The distance
between buildings is given in units of 1000 yards. These distances between buildings
are given in the table that follows. The distance from building i to building j is the
same as the distance from building j to building i.
1 2 3 4 5 6 7 8
1 - 1.6 1.4 0.5 1.2 1.5 1.8 2.3
2 - 0.9 1.8 1.2 2.6 2.3 1.1
3 - 2.6 1.7 2.5 1.9 1.0
4 - 0.7 1.6 1.5 0.9
5 - 0.9 1.1 0.8
6 - 0.6 1.0
7 - 0.5
8
Which pairs of buildings should be directly connected to connect all the buildings with
a minimum total network length? What is the length of a minimum network? What are
the different possible minimum networks?
- Assume that all the weights on the edges of a graph are positive. Prove that if no
two edges in a graph have the same weight, then the MCST is unique. (Hint: As-
sume G has more than one minimal spanning tree. Order the edges, and consider the
smallest subscript k of an edge that belongs to some, but not all, minimal spanning
trees.)
- Find an algorithm for determining an MCST that is based on removing the maximum
cost edge from a cycle at each step.
18. Let F : T -* S be an isomorphism between binary trees T and S. Let v E T be a
vertex at level k for k > 0. Prove that F(v) is at level k in S.
- For each of the following sets of words, find the binary search tree that is formed when
the underlined word is the label of the root and the remaining words are added to the
tree in left-to-right order as they occur in the sentence.
(a) The time has come for all good.
(b) The time has come for all good.
(c) The time has come for all good.
(d) Since all the words in this sentence are different, it is possible to represent them
with a binary search tree.
- Write a recursive algorithm to traverse a binary search tree and list its labels in increas-
ing order. Write the procedure so that it can be extended easily to a program in some
programming language.
- Write an algorithm for the postorder traversal of any rooted tree.
