Problem Set VII, for Monday, November 26
Mathematics 61
Introduction (to Trees)
(page 267 in Discrete Source or page 385 in Discrete Mathematics):
- Exercise 5.
- Exercise 10. Figure 1.5 is on page 263 or 381.
- Exercise 30. Can we conclude that the tree must have at
least two vertices of degree 1? Why or why not?
- Exercise 31: Trees are planar.
Terminology and Characterizations of Trees
(page 272 in Discrete Source or page 390 in Discrete Mathematics):
- Exercise 26.
- Find all values of n such that there is a simple graph
G with n vertices for which both G and
its complement are trees.
- Assume that G is a simple graph and v is a vertex
of degree 3 in G. Prove that either G or its
complement contains a triangle (i.e., a K_3 subgraph).
Spanning Trees
(page 279 in Discrete Source or page 397 in Discrete Mathematics):
- Exercise 18. Support your answer.
(Here the phrase "under what conditions" is open-ended.
You want to produce a criterion that does not mention spanning trees.)
Minimal Spanning Trees
(page 284 in Discrete Source or page 402 in Discrete Mathematics):
- Exercise 2.
Start at 1.
Also give the total weight of the minimal spanning tree constructed,
and list the vertices (starting with 1) that Prim's algorithm adds
to the minimal spanning tree, in the order in which the algorithm
adds them.
- Exercise 3.
Start at 1.
Also give the total weight of the minimal spanning tree constructed,
and list the vertices (starting with 1) that Prim's algorithm adds
to the minimal spanning tree, in the order in which the algorithm
adds them.
Isomorphisms of Trees
(page 310 in Discrete Source or page 428 in Discrete Mathematics):
Remark for Section 9.1: Huffman codes were invented by David Huffman,
the result of a term paper he wrote while a graduate student at MIT in
the 1950's. He later taught at UC Santa Cruz. He died
in 1999. Huffman codes are widely used for data compression.
Click here for answers
in .pdf format.