Logout Open In App
Open In App
Warning: foreach() argument must be of type array|object, bool given in /var/www/html/web/app/themes/studypress-core-theme/template-parts/header/mobile-offcanvas.php on line 20

Chapter 11: Q46E (page 757)

How many vertices, leaves, and internal vertices does the rooted Fibonacci tree \({T_n}\) have, where \(n\) is a positive integer? What is its height?

Short Answer

Expert verified

Number of vertices: \({{\bf{a}}_{\bf{1}}}{\bf{ = 1, }}{{\bf{a}}_{\bf{2}}}{\bf{ = 1, }}{{\bf{a}}_{\bf{n}}}{\bf{ = }}{{\bf{a}}_{{\bf{n - 1}}}}{\bf{ + }}{{\bf{a}}_{{\bf{n - 2}}}}{\bf{ + 1}}\)

Number of leaves: \({{\bf{b}}_{\bf{1}}}{\bf{ = 1, }}{{\bf{b}}_{\bf{2}}}{\bf{ = 1, }}{{\bf{b}}_{\bf{n}}}{\bf{ = }}{{\bf{b}}_{{\bf{n - 1}}}}{\bf{ + }}{{\bf{b}}_{{\bf{n - 2}}}}\)

Number of internal vertices: \({{\bf{c}}_{\bf{1}}}{\bf{ = 0, }}{{\bf{c}}_{\bf{2}}}{\bf{ = 0, }}{{\bf{c}}_{\bf{n}}}{\bf{ = }}{{\bf{c}}_{{\bf{n - 1}}}}{\bf{ + }}{{\bf{c}}_{{\bf{n - 2}}}}{\bf{ + 1}}\)

Height: \({{\bf{d}}_{\bf{1}}}{\bf{ = 0, }}{{\bf{d}}_{\bf{n}}}{\bf{ = n - 2}}\) when \({\bf{n}} \ge {\bf{2}}\)

Step by step solution

01

Definition

Rooted Fibonacci trees: \({T_1}\) and \({T_2}\) contain a single vertex. contains a root that is connected to \({T_{n - 1}}\) as its left subtree and to \({T_{n - 2}}\) as its right subtree.

02

Step 2:Finding vertices

Given: \({T_n}\) with n a positive integer.

Let \({a_n}\) represent the number of vertices in \({T_n}\)

\({T_1}\)and\({T_2}\) contain a single vertex.

\(\begin{array}{c}{a_1} = 1\\{a_2} = 1\end{array}\)

The number of vertices in \({T_3}\) is 1 increased by the number of vertices in both \({T_1}\) and \({T_2}\)

\({a_3} = 1 + {a_1} + {a_2} = 1 + 1 + 1 = 3\)

03

Step 3:Finding vertices

The number of vertices in \({T_4}\) is 1 increased by the number of vertices in both \({T_2}\) and \({T_3}\)

\({a_4} = 1 + {a_2} + {a_3} = 1 + 1 + 3 = 5\)

A similar pattern will arise for higher values of n, thus we obtain a recurred relation:

\(\begin{array}{c}{a_1} = 1\\{a_2} = 1\\{a_n} = {a_{n - 1}} + {a_{n - 2}} + 1\end{array}\)

Note: it is possible to prove (by induction) that \({a_n} = 2{f_n} - 1\) with \({f_n}\) the nth Fibonacci number.

04

Step 4:Finding leaves

Let \({b_n}\) represent the number of leaves in \({T_n}\)

\({T_1}\)and\({T_2}\) contain a single leave.

\(\begin{array}{c}{b_1} = 1\\{b_2} = 1\end{array}\)

The number of leaves in \({T_3}\) is the sum of the number of leaves in \({T_1}\) and \({T_2}\) (as the added root will not be a leave).

\({b_3} = {b_1} + {b_2} = 1 + 1 = 2\)

05

Finding leaves

The number of vertices in \({T_n}\) is the sum of the number of leaves in both \({T_2}\)and \({T_3}\).

\({b_4} = {b_2} + {b_3} = 1 + 2 = 3\)

A similar pattern will arise for higher values of n, thus we obtain a recurred relation:

\(\begin{array}{c}{b_1} = 1\\{b_2} = 1\\{b_n} = {b_{n - 1}} + {b_{n - 2}}\end{array}\)

Note: the number of leaves of \({T_n}\) is \({f_n}\) with \({f_n}\) the nth Fibonacci number.

06

Internal vertices

Let \({{\bf{c}}_{\bf{n}}}\) represent the number of internal vertices in \({T_n}\)

The number of internal vertices is the difference between the number of vertices and the number of leaves.

\(\begin{array}{c}{c_1} = {a_1} - {b_1} = 1 - 1 = 0\\{c_2} = {a_2} - {b_2} = 1 - 1 = 0\\{c_n} = {a_n} - {b_n}\\ = \left( {{a_{n - 1}} + {a_{n - 2}} + 1} \right) - \left( {{b_{n - 1}} + {b_{n - 2}}} \right)\\ = \left( {{a_{n - 1}} - {b_{n - 1}}} \right) + \left( {{a_{n - 2}} - {b_{n - 2}}} \right) + 1\\ = {c_{n - 1}} + {c_{n - 2}} + 1\end{array}\)

Note: the number of internal vertices of \({T_n}\) is \(2{f_n} - 1 - {f_n} = {f_n} - 1\) with \({f_n}\) the nth Fibonacci number.

07

Finding height

Let \({d_n}\) represent the height of a tree

The height of \({T_1}\) and \({T_2}\) are both 0 (as they contain only 1 vertex).

\(\begin{array}{c}{d_1} = 0\\{d_2} = 0\end{array}\)

The height of \({T_3}\) is 1 more than the height of \({T_2}\).

\({d_3} = {d_2} + 1 = 1\)

08

Finding height

The height of \({T_4}\) is 1 more than the height of \({T_3}\).

\({d_4} = {d_3} + 1 = 1 + 1 = 2\)

A similar pattern will arise for higher values of n, thus we obtain a recurred relation:

\(\begin{array}{c}{d_1} = 0\\{d_2} = 0\\{d_n} = {n_{n - 1}} + 2\end{array}\)

More precisely, you can note that \({T_n}\) has height \({d_n} = n - 2\)when \(n \ge 2\).

Unlock Step-by-Step Solutions & Ace Your Exams!

  • Full Textbook Solutions

    Get detailed explanations and key concepts

  • Unlimited Al creation

    Al flashcards, explanations, exams and more...

  • Ads-free access

    To over 500 millions flashcards

  • Money-back guarantee

    We refund you if you fail your exam.

Start your free trial

Over 30 million students worldwide already upgrade their learning with Vaia!

One App. One Place for Learning.

All the tools & learning materials you need for study success - in one app.

Get started for free

Most popular questions from this chapter

Show that if \(G\) is a weighted graph with distinct edgeweights, then for every simple circuit of \(G\), the edge of maximum weight in this circuit does not belong to anyminimum spanning tree of \(G\).

Sollin's algorithm produces a minimum spanning tree from a connected weighted simple graph \({\bf{G = (V,E)}}\) by successively adding groups of edges. Suppose that the vertices in \({\bf{V}}\) are ordered. This produces an ordering of the edges where \({\bf{\{ }}{{\bf{u}}_{\bf{0}}}{\bf{,}}{{\bf{v}}_{\bf{0}}}{\bf{\} }}\) precedes \({\bf{\{ }}{{\bf{u}}_{\bf{1}}}{\bf{,}}{{\bf{v}}_{\bf{1}}}{\bf{\} }}\) if \({{\bf{u}}_{\bf{0}}}\) precedes \({{\bf{u}}_{\bf{1}}}\) or if \({{\bf{u}}_{\bf{0}}}{\bf{ = }}{{\bf{u}}_{\bf{1}}}\) and \({{\bf{v}}_{\bf{0}}}\) precedes \({{\bf{v}}_{\bf{1}}}\). The algorithm begins by simultaneously choosing the edge of least weight incident to each vertex. The first edge in the ordering is taken in the case of ties. This produces a graph with no simple circuits, that is, a forest of trees (Exercise \({\bf{24}}\) asks for a proof of this fact). Next, simultaneously choose for each tree in the forest the shortest edge between a vertex in this tree and a vertex in a different tree. Again the first edge in the ordering is chosen in the case of ties. (This produces a graph with no simple circuits containing fewer trees than were present before this step; see Exercise \({\bf{24}}\).) Continue the process of simultaneously adding edges connecting trees until \({\bf{n - 1}}\) edges have been chosen. At this stage a minimum spanning tree has been constructed.

Show that the addition of edges at each stage of Sollin’s algorithm produces a forest.

Draw a game tree for him if the starting position consists of two piles with two and three stones, respectively. When drawing the tree represent by the same vertex symmetric positions that result from the same move. Find the valueof each vertex of the game tree. Who wins the game if both players follow an optimal strategy?

Answer these questions about the rooted tree illustrated.

  1. Which vertex is the root\(?\)
  2. Which vertices are internal\(?\)
  3. Which vertices are leaves\(?\)
  4. Which vertices are children of \({\bf{j}}\)\(?\)
  5. Which vertex is the parent of \({\bf{h}}\)\(?\)
  6. Which vertices are siblings of \({\bf{o}}\)\(?\)
  7. Which vertices are ancestors of \({\bf{m}}\)\(?\)
  8. Which vertices are descendants of \({\bf{b}}\)\(?\)

Build a binary search tree for the word’s oenology,phrenology, campanology, ornithology, ichthyology, limnology, alchemy, and astrology using alphabetical order.
See all solutions

Recommended explanations on Math Textbooks

Statistics

Read Explanation

Applied Mathematics

Read Explanation

Pure Maths

Read Explanation

Calculus

Read Explanation

Discrete Mathematics

Read Explanation

Theoretical and Mathematical Physics

Read Explanation
View all explanations

What do you think about this solution?

We value your feedback to improve our textbook solutions.

Study anywhere. Anytime. Across all devices.

Sign-up for free