• :00Days
• :00Hours
• :00Mins
• 00Seconds
A new era for learning is coming soon Suggested languages for you:

Europe

Answers without the blur. Sign up and see all textbooks for free! Q13SE

Expert-verified Found in: Page 805 ### Discrete Mathematics and its Applications

Book edition 7th
Author(s) Kenneth H. Rosen
Pages 808 pages
ISBN 9780073383095 # Draw $${{\bf{B}}_{\bf{k}}}$$ for $${\bf{k = 0,1,2,3,4}}$$.

Therefore, the draw of $${{\bf{B}}_{\bf{k}}}$$ for $${\bf{k = 0,1,2,3,4}}$$ is shown below. See the step by step solution

## Step 1: General form

Principle of Binomial trees: The binomial trees $${{\bf{B}}_{\rm{i}}}$$, $${\bf{i = 0,1,2,}}...{\bf{,}}$$ are ordered rooted trees defined recursively:

Basis step: the binomial tree $${{\bf{B}}_0}$$ is the tree with a single vertex.

Recursive step: Let k be a nonnegative integer. To construct the binomial tree $${{\bf{B}}_{{\bf{k + 1}}}}$$, add a copy of $${{\bf{B}}_{\bf{k}}}$$ to a second copy of $${{\bf{B}}_{\bf{k}}}$$ by adding an edge that makes the root of the first copy of $${{\bf{B}}_{\bf{k}}}$$ the leftmost child of the root of the second copy of $${{\bf{B}}_{\bf{k}}}$$.

## Step 2: Draw the rooted trees

Given that, $${\bf{k = 0,1,2,3,4}}$$.

Draw $${{\bf{B}}_{\bf{k}}}$$.

Since, $${{\bf{B}}_0}$$ contains a single vertex.

Then, $${{\bf{B}}_1}$$ contains an edge between two single vertices and one of the vertices has to be the root.

$${{\bf{B}}_2}$$ contains two copies of $${{\bf{B}}_1}$$ with an edge from the root of one copy to the root of the other copy.

Note: you then also need to place the root of the left copy at level 1 along with the rest of the copy.

$${{\bf{B}}_3}$$contains two copies of $${{\bf{B}}_2}$$ with an edge from the root of one copy to the root of the other copy.

$${{\bf{B}}_4}$$contains two copies of $${{\bf{B}}_3}$$ with an edge from the root of one copy to the root of the other copy.

The graph is shown below. Conclusion: The above graph represents the $${{\bf{B}}_{\bf{k}}}$$ for $${\bf{k = 0,1,2,3,4}}$$. ### Want to see more solutions like these? 