CPTS553 Assignment 6 Solved

30.00 $ 15.00 $

Category:
Click Category Button to View Your Next Assignment | Homework

You'll get a download link with a: . zip solution files instantly, after Payment

Description

Rate this product

 

Questions with a (⋆) are each worth 1 bonus point for 453 students.

  1. Show that for any π‘˜ β‰₯ 3, if a tree 𝑇 has fewer than π‘˜ leaves, then the maximum degree Ξ”(𝑇) among the vertices of 𝑇 must satisfy Ξ”(𝑇) < π‘˜. It can help to consider the summations

𝑛  𝑛𝑗 ;Β Β Β Β Β Β Β  2(𝑛 βˆ’ 1) = total degree .

𝑗=1Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β  𝑗=1

The phrase β€œπ‘‡ has fewer than π‘˜ leaves” means 𝑛1 < π‘˜.

The two sums can be combined into the single sum

𝑛

βˆ‘(2 βˆ’ 𝑗)𝑛𝑗 = 2

𝑗=1

It suffices to show that 𝑛𝑗 = 0 for all 𝑗 β‰₯ π‘˜.

 

  1. Let (𝑇, π‘Ÿ) be a rooted tree. Recall that the level of a vertex π‘₯ is 𝐿(π‘₯) = 𝐷(π‘Ÿ, π‘₯).Β  Also, the height of a rooted tree 𝐻 is the maximum of the levels of its vertices.
    1. Show that if π‘Ÿ is on the unique 𝑒, 𝑣-path, then 𝐷(𝑒, 𝑣) = 𝐿(𝑒) +

𝐿(𝑣).

  1. Show that if 𝐿(𝑒) + 𝐿(𝑣) = 𝐷(𝑒, 𝑣), then π‘Ÿ must be on the unique 𝑒, 𝑣-path.
  2. Show that for any two vertices 𝑒 and 𝑣, 𝐷(𝑒, 𝑣) ≀ 2𝐻.
  3. Show that if 𝐷(𝑒, 𝑣) = 2𝐻, then 𝑒 and 𝑣 must be non-parents. Equivalently, you can show that if either 𝑒 or 𝑣 is a parent, then 𝐷(𝑒, 𝑣) < 2𝐻.

 

  1. Suppose (𝑇, π‘Ÿ) is a rooted π‘ž-ary tree where every parent has exactly π‘ž children; such a tree is said to be saturated.
    1. Show that 𝑇 has π‘π‘ž edges for some integer 𝑏.
    2. Find a formula for the number of vertices of 𝑇 in terms of 𝑏, π‘ž.
    3. Find a formula for the number of non-parents in terms of 𝑏, π‘ž.

 

  1. Suppose (𝑇, π‘Ÿ) is a rooted tree with exactly 1012 Recall that a lower bound or an upper bound on 𝐻 is tight if there exists an example 𝑇 where that bound is attained.
    1. Find tight lower and upper bounds for 𝐻, the height of 𝑇.
    2. Find tight lower and upper bounds for 𝐻 if 𝑇 is a saturated rooted binary tree. Recall that saturated means every parent has the maximum allowed number of children; here, that number is 2.