# 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.