Tags:
, view all tags
Quick Answers - Homework Assignment 5

1. Suppose a connected graph G has 20 edges. What is the maximum number of vertices possible in G?

Answer: 21 - this is the tree on 21 vertices

2. Let T be a (an undirected) tree. If the choice of x to be root yields a rooted tree of minimum height, then x is said to be a center of T. Show that any undirected tree has at most 2 centers.

Answer: T can be made directed, with some node x as root. If x is the center with neighbors a,b,c,d... and 2 of the subtrees rooted at this level contain leaves of max level k, then x is the unique center (replacing x by any of a,b,c.. would yield a tree of height k+1). If (only) x neighbor p has a leaf at level k in original tree (leaves on other subtrees are all at lower levels), then p could also be a center - some x neighbor q must then have a leaf at level k-1 in T rooted at x, which would now be at level k in tree rooted at p.

Alternate Answer: show that if x and y are both centers in T, then they must be adjacent.

3. Suppose that a chain letter is started by someone in the first week of the year. Each recipient of the chain letter mails copies on to five other people in the next week. After six weeks, how much money in total is spent on postage (figure 50¢ per letter)?

Answer: there are 5**6 leaves L. By thm in text, N = (mL -)/(m-1). So N = (5**7 - 1)/4. All but one of these (the root) cost 50 cents.

4. Construct trees with the following Prufer sequences: (4,5,6,2); (2,8,8,3,5,4)

5. Let T be an m-ary tree with n vertices, consisting of i internal nodes and L leaves. Suppose m is even. Show that n always has to be odd. Give two small examples for a fixed m that shows that i can be either even or odd.

Answer: since n = m*i + 1, m*i is even and thus n is odd.

6. Three jealous wives and their husbands come to a river. The party must cross a river in a boat that holds at most 2 people. Find a sequence of boat trips that will get the six people across the river without ever leaving any husband alone (without his wife) with another wife. Note: an unmarried husband/wife pairing is also not allowed for the boat crossing.

Wives are ABC, husbands abc on near shore.

ab across, a returns: ABCac/b

ac across, a returns: ABCa/bc

BC across, Bb returns: ABab/Cc;

AB across, c returns: abc/ABC

ac across, c returns: bc/ABCa

then bc across

7. Suppose the degree sequence of a tree looks like this: (6,5,4,3,2,1….1). Determine how many 1’s there are in the sequence.

Answer: use these equations, assuming there are k 1's:

V = 5+k; V = E+1; 20+k = 2E (by handshaking lemma). So k = 12.

-- RobbieMoll - 2012-03-05

Edit | Attach | Print version |  | Backlinks | Raw View | Raw edit | More topic actions...
Topic revision: r4 - 2012-03-06 - RobbieMoll

 Home Moll575 Web View Edit Account
 Edit Attach
Copyright © 2008-2019 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding UMass CS EdLab? Send feedback