Base cases I(1) = I(2) = I(3) = 0 & I(4) = 1 but for the recurrence, n>=5 I(n) =

Question

Base cases I(1) = I(2) = I(3) = 0 & I(4) = 1

but for the recurrence, n>=5 I(n) = 2 + I(n-1) + I(n-2) until I(n-2) or I(n-1) is I(5)?

1. Let Ti be the rooted tree consisting of a single vertex. Let T2 T. For n 3. let Tn be the rooted tree whose left subtree is T and whose right subtree is T n-2 n-1 (c) (2 points) Let I (n) be the number of internal vertices in Tn. Find a recurrence that I (n) satisfies. (d) (2 points) Let V(n) be the number of vertices in Trn. Find a recurrence that V(n) satisfies. (e) (2 points) Let E(n) be the number of edges in Tn. Find a recurrence that E(n) satisfies.

Explanation / Answer

C)

I(1) and I(2) is zero but I(3) is 1 due to root node is the internal node(or vertices).

So for every n>=3,

                I(n) = 1 + I(n-2) + I(n-1)

It will give the total no of vertices in the graph

D)

V(0) is 0

V(n) = 1 + V(n-2) + V(n-1)

E)

                E(0) is 0

                E(n) = (n-1) + E(n-1)

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.